# 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. Sep 24, 2015 at 12:18
• Which paper are you reading?
– j.c.
Sep 24, 2015 at 14:16
• @j.c. It is likely Universality Considerations in VLSI Circuits computer.org/csdl/trans/tc/1981/02/06312176.pdf Sep 24, 2015 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. Sep 24, 2015 at 14:51
• Is there a mistake in the paper? Sep 24, 2015 at 14:54

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

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). Sep 24, 2015 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. Sep 24, 2015 at 15:00
• @Tony Huynh when you say union you mean a collection of horizontal and vertical lines joined by bends? Sep 24, 2015 at 15:32
• Yes, and the bends can only happen at integer points (the vertices are also constrained to lie on integer points). Sep 24, 2015 at 15:58
• Regarding the $O(|V|)$ should it be $O(|V|^{2})$? Sep 24, 2015 at 16:11