Embedding a general planar graph into a grid

I have here a little problem with my homework, and would appreciate some direction.

I am attempting for some time now to show that every planar graph is embeddable into a grid (As large as needs be).

I tried to make this argument inductively in many ways, but I am afraid that I don't see any good way to do that so far. My main problem is that while the subgraph may be embeddable in a grid, it might not still be possible to connect the relevant nodes to the nodes added in the inductive stage after the reorganization.

While writing this down, I thought of another possible solution which might solve it - observing the embedding to the plain as an embedding in the Cartesian plane, and moving every node to a "very close" point whose both coordinates are rational. Taking the greatest common denominator of all the coordinates, I believe that I'll find myself in a (huge) grid as required.

• How would you embed a degree-5 vertex? $\;$ – user12859 Jun 2 '14 at 17:50
• @RickyDemer. I'm confused. Is this a question, or a hint? – Rick Decker Jun 3 '14 at 1:23
• @RickDecker : $\:$ That is a question. $\;\;\;\;$ – user12859 Jun 3 '14 at 1:28
• What do you know about planar graphs? Do you know any method how to draw a planar graph, like Tutte's barycentric embeddings? Do you consider straight-line embeddings? Do you know Fary's theorem? – A.Schulz Jun 3 '14 at 8:48

2 Answers

There is a really neat result which answer's this question: Schnyder's Theorem. Another nice result is that of de Fraysseix, Pach and Pollack.

Here is a reference for both algorithms. The "Realizer Method" corresponds to Schnyder's Theorem and "Canonical Orderings" corresponds to de Fraysseix et al.'s approach.

These algorithms can embed any planar triangulation in an $$O(n)\times O(n)$$ grid. You can embed a planar graph $$G$$ by adding edges until you obtain a maximal planar graph $$T$$. Then you run any of these algorithms with input $$T$$. The output will be a drawing of $$T$$ in an $$O(n)\times O(n)$$ grid, which is also a drawing of $$G$$ in that same grid.

Do you know Fáry's Theorem? It proves that any planar graph has an embedding where each edge is a straight line. It's not too difficult to modify this to a grid, as you indicate in your last paragraph. I haven't tried it in detail, but I suspect the minutia would require a bit of care

• One of the minutia would be definitional, since vertices in the square grid only have degree 4. $\hspace{.8 in}$ – user12859 Jun 3 '14 at 1:30
• @RickyDemer. Why should that be? Five neighbors of $(0,0)$ could be $(-1,0),(1,0),(0, -1),(0,1),(1,1)$. – Rick Decker Jun 3 '14 at 1:37
• That should be because an edge from $\langle 0,\hspace{-0.03 in}0\rangle$ to $\langle \hspace{-0.02 in}1\hspace{-0.02 in},\hspace{-0.04 in}1\hspace{-0.02 in}\rangle$ would create a triangle. $\:$ – user12859 Jun 3 '14 at 1:44
• @RickyDemer. Ah. I think I see the source of our confusion. I read the OP as saying that the vertices were restricted to the grid points (it seems that we agree here), but I took her formulation to allow edges in the embedding that weren't grid edges. – Rick Decker Jun 3 '14 at 1:54
• Ooh, that would explain it. $\;$ – user12859 Jun 3 '14 at 2:00