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.

  • 1
    $\begingroup$ How would you embed a degree-5 vertex? $\;$ $\endgroup$ – user12859 Jun 2 '14 at 17:50
  • $\begingroup$ @RickyDemer. I'm confused. Is this a question, or a hint? $\endgroup$ – Rick Decker Jun 3 '14 at 1:23
  • $\begingroup$ @RickDecker : $\:$ That is a question. $\;\;\;\;$ $\endgroup$ – user12859 Jun 3 '14 at 1:28
  • 2
    $\begingroup$ 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? $\endgroup$ – A.Schulz Jun 3 '14 at 8:48

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

  • $\begingroup$ One of the minutia would be definitional, since vertices in the square grid only have degree 4. $\hspace{.8 in}$ $\endgroup$ – user12859 Jun 3 '14 at 1:30
  • $\begingroup$ @RickyDemer. Why should that be? Five neighbors of $(0,0)$ could be $(-1,0),(1,0),(0, -1),(0,1),(1,1)$. $\endgroup$ – Rick Decker Jun 3 '14 at 1:37
  • $\begingroup$ 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. $\:$ $\endgroup$ – user12859 Jun 3 '14 at 1:44
  • $\begingroup$ @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. $\endgroup$ – Rick Decker Jun 3 '14 at 1:54
  • $\begingroup$ Ooh, that would explain it. $\;$ $\endgroup$ – user12859 Jun 3 '14 at 2:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.