# 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.

1. Although not explicitly stated i assume the embedding is planar too?
2. 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?
• By some sort of continuity argument, one can always take the points of a planar embedding to be in $\mathbb Q \times \mathbb Q$, and then scale everything up so that the coordinates will all be integers. So the $O(|V|)$ bound would really seem to be the essential aspect of the result. – Louis Deaett Sep 24 '15 at 12:18
• Which paper are you reading? – j.c. Sep 24 '15 at 14:16
• @j.c. It is likely Universality Considerations in VLSI Circuits computer.org/csdl/trans/tc/1981/02/06312176.pdf – Tony Huynh Sep 24 '15 at 14:27
• Hi guys, just make sure i haven't misstated Valiant's result here is the paper where i found it stated ac.els-cdn.com/0012365X9090358O/… it's on page 4 of the document under lemma 2.1. And yes the paper i'm referring to is the one mentioned above. – Pavan Sangha Sep 24 '15 at 14:51
• Is there a mistake in the paper? – Pavan Sangha Sep 24 '15 at 14:54

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

There is a huge literature on this topic. Search for "orthogonal graph drawing". The best possible area bound is $O(n^2)$.

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.

• It looks like this algorithm does not require edges to be orthogonal to the $x$ and $y$ axis (i.e edges are horizontal and vertical lines). – Pavan Sangha Sep 24 '15 at 14:02
• @CBrosen Note that in rectilinear embeddings the edges are not horizontal and vertical lines; they are a union of horizontal and vertical line segments. – Tony Huynh Sep 24 '15 at 15:00
• @Tony Huynh when you say union you mean a collection of horizontal and vertical lines joined by bends? – Pavan Sangha Sep 24 '15 at 15:32
• Yes, and the bends can only happen at integer points (the vertices are also constrained to lie on integer points). – Tony Huynh Sep 24 '15 at 15:58
• Regarding the $O(|V|)$ should it be $O(|V|^{2})$? – Pavan Sangha Sep 24 '15 at 16:11