The following question arose when I was trying to find explicit topological embeddings of bounded degree graphs into $\mathbb R^3$ which match (asymptotically) the minimal possible "volume" of such an embedding given by Kolmogorov-Barzdin. This doesn't actually help (as far as I can tell), but it seemed interesting so I wanted to share it.
Do there exist universal constants $A,C$ such that for every simple graph $G$ with $n^2$ vertices and maximal degree $3$ there is an injective function $f:V(G)\to \{1,\ldots,An\}^2$ such that for every $1\leq i,j \leq An$ the number of edges with one end vertex in $f^{-1}\left(\{i\}\times \{1,\ldots,An\}\right)$ and the other in $f^{-1}\left(\{1,\ldots,An\}\times\{j\}\right)$ is at most $C$.
