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?