I've seen the following lemma in a paper. The result is by Valiant.

A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at integer coordinates and its edges are drawn so that they are made up of line segments of the form $x=i$ or $y=j$, for integers $i$ and $j$.

I have two questions.

- Although not explicitly stated i assume the embedding is planar too?
- Is there anything regarding the shape of the area that the graph is embedded into other than the fact it's area is $O(|V|)$ ? More specifically can we for example ensure that the graph can be embedded in a $|V|\times |V|$ grid?

Universality Considerations in VLSI Circuitscomputer.org/csdl/trans/tc/1981/02/06312176.pdf $\endgroup$ – Tony Huynh Sep 24 '15 at 14:27