Embedding planar graphs into the grid 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? 

 A: As far as I understand, I think you have misstated Valiant's result.
Regarding $1$, yes the embedding is assumed to be planar, with the edges constrained to follow the 'edges' of the grid.  This is called a rectilinear embedding.  Note that only graphs with maximum degree 4 have rectilinear embeddings, hence the degree restriction.  Secondly, the area of the embedding is defined to be the area of the smallest box bounding the embedding. Thus, the $O(V)$ area condition is quite strong (in particular, the length or width is $O(\sqrt V)$).  Finally, Valiant's result is actually for trees with maximum degree $4$.  He showed that the $O(V)$ area condition is false in general; there are planar graphs with maximum degree 4 that require bounding area $O(V^2)$.
Edit.
For the benefit of others who have not followed the chat, here is a summary. The lemma  under consideration is Lemma 2.1 of the paper Unit Disk Graphs by Clark, Colbourn and Johnson.  The lemma is due to Valiant, but a typo was  was introduced by Clark, Colbourn and Johnson.  The $O(|V|)$ should be replaced by $O(|V|^2)$.
A: There is a huge literature on this topic. Search for "orthogonal graph drawing". The best possible area bound is $O(n^2)$. 
A: Yes. I am not sure what Valiant proved, but as far as I know, the best result on planar graph embedding in the grid is Schnyder's algorithm.. De Fraysseix, Pach, Pollack (1990) show that an $n$-vertex graph can be embedded in a $n-2 
\times 2n -4 $ grid.
