Part 17: Planar Graphs & Topological Graph Theory

A Bit of History

Planarity questions are as old as graph theory itself — the Seven Bridges of Königsberg from Part 12 was really a question about a graph drawn on a specific map. But the mathematics of "can this be drawn without crossings, and what happens if we insist it can't" crystallized a century after Euler, through three landmark results:

• Leonhard Euler himself, in 1750, discovered a strikingly simple relationship for convex polyhedra — vertices minus edges plus faces always equals 2 — while cataloging the Platonic and Archimedean solids. It would take another century before mathematicians recognized this as a statement about planar graphs.
• Kazimierz Kuratowski, a leading figure of the Warsaw School of mathematics, published in 1930 a complete characterization of planarity: a graph is planar if and only if it contains no subdivision of the two smallest non-planar graphs, \(K_5\) and \(K_{3,3}\).
• Klaus Wagner, a German graph theorist, proved an equivalent (and more powerful) version in 1937 using the more permissive notion of a graph minor rather than subdivision — a distinction that would later become central to the Robertson-Seymour theory explored in Part 18.

Planarity Fundamentals

A graph \(G\) is planar if it can be drawn in the plane so that no two edges cross (except at shared endpoints). Such a drawing is called a planar embedding. A planar embedding divides the plane into regions called faces, including one unbounded outer face.

Two small graphs turn out to be the seeds of all non-planarity:

• \(K_5\) — the complete graph on 5 vertices (every pair connected). No matter how you arrange 5 mutually-connected points, some pair of edges must cross.
• \(K_{3,3}\) — the complete bipartite graph on two groups of 3 (the classic "three houses, three utilities" puzzle: can each of 3 houses be connected to each of 3 utility companies — gas, water, electric — without any connection lines crossing? It cannot).

Euler's Formula

For any connected planar graph drawn in the plane with \(V\) vertices, \(E\) edges, and \(F\) faces (including the outer face):

$$V - E + F = 2$$

This holds regardless of which planar embedding you draw — a remarkable invariant. Two immediate and extremely useful corollaries follow for simple planar graphs with \(V \geq 3\):

$$E \leq 3V - 6 \qquad \text{(general simple planar graphs)}$$

$$E \leq 2V - 4 \qquad \text{(bipartite planar graphs, since every face has at least 4 edges)}$$

Kuratowski's & Wagner's Theorems

Kuratowski's Theorem (1930): A graph is planar if and only if it contains no subgraph that is a subdivision of \(K_5\) or \(K_{3,3}\) (a subdivision replaces edges with paths — inserting degree-2 vertices along edges without changing the underlying connectivity structure).

Wagner's Theorem (1937): A graph is planar if and only if it contains no minor isomorphic to \(K_5\) or \(K_{3,3}\) (a minor is obtained by deleting vertices/edges and contracting edges — a strictly more powerful reduction than subdivision, since contraction can simplify a graph subdivisions cannot).

The two theorems describe the exact same class of graphs (planar graphs), phrased in two different — but provably equivalent for this purpose — reduction operations. Wagner's minor-based formulation turned out to generalize spectacularly: it is the direct ancestor of the sweeping Robertson-Seymour graph minor theorem, which shows that every minor-closed graph family (not just planar graphs) has a finite forbidden-minor characterization — the subject of Part 18.

Beyond the Plane: Genus

Not every graph is planar, but every graph can be drawn without crossings on some surface — if you're allowed enough "handles." The genus of a graph is the minimum number of handles (equivalently, donut-holes) a surface needs so the graph embeds on it without crossings. Planar graphs have genus 0 (they embed on a plane/sphere); \(K_5\) and \(K_{3,3}\) both have genus 1 (they embed on a torus — try drawing the "three houses, three utilities" puzzle on the surface of a donut, and it suddenly becomes solvable).

Euler's formula generalizes to any surface of genus \(g\):

$$V - E + F = 2 - 2g$$

A closely related and highly practical question is whether a planar graph can be drawn with all edges as straight line segments (not just curves). Fáry's theorem (proved independently by István Fáry in 1948, and earlier by Klaus Wagner in 1936 and Sherman Stein in 1951) answers yes: every planar graph has a straight-line planar embedding — a fact quietly relied upon by every graph-drawing and circuit-layout tool in existence.

Planarity Testing Algorithms

Kuratowski's and Wagner's theorems are elegant characterizations, but naively searching for a forbidden subdivision or minor is far too slow for practical use. The breakthrough came from two familiar names: John Hopcroft and Robert Tarjan — the same pair (individually) behind Hopcroft-Karp matching and Tarjan's SCC algorithm from earlier deep dives — published a linear-time \(O(V)\) planarity testing algorithm in 1974, based on a clever DFS-driven edge-addition strategy. It remains one of the most celebrated results in algorithmic graph theory precisely because linear time feels almost too fast for a problem that looks combinatorially explosive on the surface.

Real-World Applications

Exercises

1. Use the \(E \leq 3V - 6\) bound to determine whether the Petersen graph (10 vertices, 15 edges) could possibly be planar. (It is, in fact, non-planar — verify the bound is satisfied here anyway, showing the bound is necessary but not sufficient.)
2. Draw \(K_4\) (complete graph on 4 vertices) as a planar embedding, and verify Euler's formula \(V - E + F = 2\) holds for your specific drawing.
3. Explain, in your own words, why a subdivision of \(K_{3,3}\) inside a larger graph is enough to prove that larger graph non-planar, using Kuratowski's theorem.
4. Challenge: Research the "three utilities puzzle" and explain precisely how embedding it on a torus (genus 1 surface) resolves the puzzle, connecting this to the genus formula given above.

Conclusion & Next Steps

Planarity turns an intuitive drawing question — "can I avoid crossings?" — into precise, checkable mathematics via Euler's formula and the Kuratowski/Wagner forbidden-subgraph theorems. That same minor-based thinking scales up dramatically in the next part, where the Robertson-Seymour theorem shows that any property closed under taking minors — not just planarity — has a similarly finite, checkable characterization.