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

Question

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.

Explanation / Answer

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)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.