As far as I understand, I think you have misstated Valiant's result.

Regarding $1$, yes the embedding is assumed to 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)$.

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)$.

As far as I understand, I think you have misstated Valiant's result.

Regarding 1, yes the embedding is assumed to 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)$.

As far as I understand, I think you have misstated Valiant's result.

Regarding $1$, yes the embedding is assumed to 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)$.