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).
A Crossing in the Picture Does Not Automatically Mean the Graph Is Non-Planar
Planarity is a property of the abstract graph, not of one unlucky sketch. You may move vertices and bend edges as much as you like, provided you preserve which vertices are connected. The same graph can therefore have a messy drawing with crossings and also a clean planar embedding with none.
Memory Rule: Planar Means “There Exists a Crossing-Free Drawing”
You do not have to make the first drawing crossing-free. You only need to prove that some drawing exists. To prove a graph non-planar, you must show that every possible drawing is forced to cross.
Euler's Formula
For any connected planar graph drawn in the plane with \(V\) vertices, \(E\) edges, and \(F\) faces (including the outer face):
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\):
Faces Are Part of the Combinatorics, Not Just Empty Space
A planar embedding partitions the plane into regions. The outside region counts too. For a planar drawing of \(K_4\), there are four vertices, six edges, and four faces, so Euler's invariant is visible directly: \(4-6+4=2\).
Where the Planar Edge Bounds Come From
The key counting fact is that every edge borders two face-sides, so the sum of all face-boundary lengths is \(2E\). In a simple planar graph every face has length at least 3, giving \(3F\le 2E\). Combine that with Euler's formula and the edge bound drops out:
For a bipartite planar graph there are no odd cycles, so in particular there are no triangular faces. Every face has boundary length at least 4, yielding the stronger bound:
triangle faces may exist → use 3F ≤ 2E
no triangles → use 4F ≤ 2E
These bounds are necessary tests, not complete planarity tests.
Key Insight
These edge bounds are exactly what prove \(K_5\) and \(K_{3,3}\) non-planar without needing to try every possible drawing. \(K_5\) has \(V=5, E=10\), but \(3V-6=9 < 10\) — too many edges for planarity, immediately. \(K_{3,3}\) has \(V=6, E=9\) and is bipartite, but \(2V-4=8 < 9\) — again immediately too many edges. Euler's formula turns an infinite search over drawings into simple arithmetic.
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.
Subdivision “Stretches” Edges; a Minor Can Also Contract Them
Kuratowski and Wagner use different reduction languages. A subdivision keeps the same branching structure and merely replaces an edge by a path through degree-2 vertices. A minor allows deletions plus edge contractions, so it can compress a larger graph down to a hidden forbidden core.
Forbidden-Core Mental Model
A non-planar graph may look nothing like \(K_5\) or \(K_{3,3}\) at first glance. Kuratowski says one of those cores appears after stretching its edges into paths; Wagner says one appears after suitable deletions and contractions. Either obstruction is a certificate that no crossing-free drawing can exist.
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 orientable surface of genus \(g\):
A Handle Gives Edges Another Way Around
On the plane, two routes may be forced to cross because there is nowhere else to go. A torus adds a handle: an edge can travel through the hole and return on the other side, avoiding an intersection that was unavoidable in the plane. Genus asks for the minimum number of handles needed for a crossing-free embedding.
Genus Is Not the Same as Crossing Number
Genus asks how many handles are needed to remove all crossings on a surface. Crossing number asks for the minimum number of edge crossings if you insist on staying in the plane. They measure different kinds of complexity.
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 planarity testing algorithm in 1974, based on a clever DFS-driven edge-addition strategy. Measured against the graph representation, this is \(O(V+E)\) time. 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.
Planarity Testing Does Not Search Through Drawings
A naive approach would try vertex positions and edge curves—an enormous geometric search. Linear-time planarity algorithms instead reason about the combinatorial embedding: the cyclic order in which edges can appear around vertices and the constraints imposed as DFS discovers more of the graph.
The standard complexity statement is linear in the graph representation size, \(O(V+E)\). The surprising part is not just speed: a practical planarity test can also produce a planar embedding when the answer is yes, or information leading to a forbidden obstruction when the answer is no.
Real-World Applications
Printed Circuit Board & VLSI Layout
Single-layer printed circuit boards and some chip-routing layers cannot let two conductive traces cross unless the design provides a deliberate connection, so a crossing-free routing is naturally modeled by planarity. If the required connection graph cannot be embedded on one layer, engineers may reroute, introduce vias, or move traces to additional layers. Extra PCB layers provide additional routing freedom, but they are an engineering analogue rather than literally the same invariant as graph genus; practical via minimization also depends on geometry, component placement, and manufacturing rules beyond Euler's formula.
Planarity Mental Model
Can I rearrange the graph so no edges cross?
Euler's formula and edge bounds can quickly rule some graphs out.
K₅ or K₃,₃ hidden as a subdivision/minor proves non-planarity.
Genus asks how many handles are needed for a crossing-free surface embedding.
Exercises
- 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.)
- 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.
- 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.
- 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.
Next in the Series
In Part 18: Special Graph Families, Isomorphism & Minors, we'll explore chordal and perfect graphs, the graph isomorphism problem, and the sweeping Robertson-Seymour graph minor theorem.