Planarity Testing — Linear Time

Planarity: definition and intuition

A graph is planar if it admits a drawing in the Euclidean plane where vertices are points and edges are curves with no crossings except at endpoints. The precise mathematical definition involves topological embeddings and planar subdivisions, but the geometric intuition is immediate: no edge should ever have to jump over another.

Planarity is a global property; you cannot decide it by inspecting one edge or vertex. A graph with millions of edges can be planar, and adding a single edge might violate it. Two small, concrete non-planar graphs emerge as canonical obstructions:

• K₅: complete graph on 5 vertices, 10 edges. No planar drawing exists.
• K₃,₃: complete bipartite 3+3 vertices, 9 edges. Also no planar drawing.

Kuratowski proved in 1930 that these two graphs, and their subdivisions, are the only fundamental obstructions. Wagner later gave an equivalent characterization using graph minors instead. These theorems are the conceptual foundation; algorithms are the practical consequence.

Euler's formula and quick rejection tests

Before running a complex algorithm, cheaper tests can often reject non-planar graphs. Euler's formula for connected planar graphs states: V − E + F = 2, where V is vertices, E is edges, and F is the number of faces (regions) in any planar drawing. Rearranging: E = V + F − 2. Since each face is bounded by at least 3 edges and each edge bounds at most 2 faces, we get E ≤ 3V − 6 for any planar graph with V ≥ 3.

This gives an immediate necessary (but not sufficient) condition: if E > 3V − 6, the graph is definitely not planar. A quick sanity check before heavier algorithms. Similarly, for bipartite planar graphs, the bound tightens to E ≤ 2V − 4. Counterexample tests: K₅ has 5 vertices and 10 edges; 3×5 − 6 = 9, so 10 > 9 confirms non-planarity. K₃,₃ has 6 vertices and 9 edges; 3×6 − 6 = 12, so E ≤ 12 passes this test—but the bipartite bound 2×6 − 4 = 8, so 9 > 8 rejects it.

Modern implementations typically apply this check first: O(1) rejection of obviously non-planar graphs before invoking the linear-time algorithm.

Kuratowski's theorem: forbidden subgraphs

Kuratowski (1930): A finite graph is planar if and only if it contains no subdivision of K₅ or K₃,₃.

A subdivision means replacing edges with paths (inserting vertices of degree 2). For example, a path from A to B is a subdivision of a single edge. The theorem says planarity is entirely characterized by the absence of two obstruction patterns, up to topological detail (subdividing edges).

Conceptually powerful: planarity is a forbidden pattern problem. Practically challenging: checking for a subdivision of K₅ or K₃,₃ requires pattern-matching that is expensive if done naively. Kuratowski's theorem is the reason we believe planarity testing is tractable at all—it reduces an infinite topological property to a finite checklist. However, extracting that Kuratowski obstruction (a minimal non-planar subgraph as a witness) is harder than deciding planarity alone; the Boyer-Myrvold algorithm can do both.

Wagner's theorem: graph minors

Wagner (1937): A finite graph is planar if and only if it has no minor that is isomorphic to K₅ or K₃,₃.

A graph minor is obtained by deleting vertices and edges, and contracting edges (merging two vertices and their neighbors). Wagner's formulation is equivalent to Kuratowski's but uses minors instead of subdivisions. Both characterizations lead to the same conclusion: planarity is the absence of K₅ and K₃,₃ (in some form).

The minor characterization is theoretically elegant—it hints at deep results like the Robertson-Seymour theorem—but algorithmically, testing for minors directly is at least as hard as testing for subdivisions. The real payoff is theoretical: planarity belongs to the class of graph properties decidable by forbidden minors, and this insight has shaped decades of structural graph theory.

Linear-time testing: DFS and the challenge

Kuratowski and Wagner tell us what to look for but not how to look efficiently. Naive enumeration of all subgraphs and minors is exponential. The breakthrough came in 1974 when Hopcroft and Tarjan showed planarity testing is in O(V+E)—the same cost as reading the input.

The key insight: planarity testing is not membership-checking for a forbidden pattern; it is constructive proof. Given a graph G, build a planar embedding step by step. If you succeed, G is planar. If you reach a contradiction, G is not. The construction uses DFS to find a spanning tree, then repeatedly attempts to add back-edges (non-tree edges) in a specific order such that no edge ever needs to cross. If all back-edges fit without crossing any existing edge or any other back-edge, the graph is planar; otherwise, it is not.

This strategy—called path addition in Hopcroft-Tarjan—is elegant because it converts the global planarity question into a sequence of local, DFS-driven choices.

Hopcroft-Tarjan: DFS tree + path addition

Algorithm outline: Run DFS from an arbitrary root to build a spanning tree T. For each non-tree edge (back-edge) e, find the unique path in T between its endpoints. This path divides the plane into two regions (inside and outside). The back-edge e must lie in one of these regions—choose greedily.

Two back-edges e₁ and e₂ conflict if their paths (in T) are nested: e₁'s path is entirely within e₂'s path or vice versa, and both edges would need to cross to stay in their regions. Planarity fails if and only if such a conflict occurs.

The algorithm works via a clever data structure (intervals and nesting checks on a DFS stack) to detect conflicts in O(1) per edge. With proper implementation, the total is O(V+E). However, the algorithm is notoriously complex to code correctly; most textbooks present a simplified version that runs in O(V log V) or O(E) with lower constant factors.

Why linear time is hard: you need to track nested path intervals on the DFS tree, recognize conflicts instantly, and backtrack sensibly when a conflict is found. Modern libraries often prefer Boyer-Myrvold (edge addition with left-right characterization) which is simpler to implement and still O(V+E).

Boyer-Myrvold and the left-right criterion

In 1999, Boyer and Myrvold published a cleaner O(V+E) algorithm using edge addition instead of path addition. The key innovation is the left-right planar embedding and the de Fraysseix-Rosenstiehl left-right criterion.

Instead of building a spanning tree and adding back-edges, Boyer-Myrvold grows the planar embedding incrementally: add one edge at a time, maintaining the invariant that the current subgraph is planar. When adding a new edge (u,v), find a path of already-embedded edges from u to v, and decide on which side of existing structure to insert the new edge. The left-right criterion is a fast test (O(1) per check) to detect forbidden configurations.

Boyer-Myrvold has two major advantages: (1) it is simpler and faster in practice (fewer bookkeeping details than Hopcroft-Tarjan), and (2) it naturally extracts a Kuratowski obstruction (minimal non-planar subgraph) when the graph fails, providing a witness. NetworkX and Boost Graph Library both use Boyer-Myrvold (or LR-based) algorithms for production planarity testing.

Biconnected components and decomposition

Planarity decomposes cleanly over biconnected components: a graph is planar if and only if all its biconnected components are planar. A biconnected component is a maximal subgraph with no cut-vertices (articulation points)—removing any single vertex does not disconnect it.

Implication: standard preprocessing is to (1) find all biconnected components in O(V+E) via DFS, (2) test each component independently, (3) concatenate results. This often speeds up practice because many real-world graphs fragment into small components. Also, the test algorithm (Hopcroft-Tarjan, Boyer-Myrvold) is usually stated and analyzed for biconnected inputs; testing a general graph formally requires this decomposition step.

Once all biconnected components are embedded planar, combining them is trivial: glue them at shared cut-vertices in any order, on any side, and the result remains planar. This composability is why biconnectivity is the "right" granularity for planarity algorithms.

Applications and why planarity matters

VLSI circuit layout: Routing wires without crossings reduces interference and simplifies manufacturing. Checking if a circuit graph is planar tells designers whether a single-layer or multi-layer design is necessary.

Graph drawing and visualization: Planar graphs admit straight-line embeddings (every edge as a straight line, still planar). Visualization algorithms for non-planar graphs must either tolerate crossings or relax the embedding to higher dimensions (e.g., 3D, or introduce dummy nodes).

Topological and structural analysis: Planarity is a proxy for "simplicity." Social networks, transportation networks, and mesh graphs often have low planarity; detecting non-planarity signals high connectivity or complex dependencies.

Outerplanarity and beyond: Outerplanar graphs (planar + all vertices on outer face) are even more constrained; they admit O(V) algorithms for many problems. Recognizing outerplanarity is a specialization of planarity testing.

Comparison of algorithms and implementation tradeoffs

Hopcroft-Tarjan (1974): First linear-time algorithm. Theory: O(V+E). Practice: complex bookkeeping, hard to implement correctly, not commonly used in libraries.

Booth-Lueker (1976): Uses PQ-trees (complex data structure) for vertex-addition. Also O(V+E) but rarely implemented.

Boyer-Myrvold (1999): Edge-addition with LR criterion. O(V+E), simpler than Hopcroft-Tarjan, extracts obstruction. De facto standard in modern libraries (NetworkX: check_planarity, Boost: boyer_myrvold_planarity_test).

Simplified O(E) algorithms: Many textbooks present O(E) variants that drop the biconnected decomposition or use simpler conflict detection. Good for teaching, acceptable for small inputs (E ≤ 10⁴). Prefer Boyer-Myrvold for real graphs.

Practical considerations and common pitfalls

Empty and trivial graphs: The empty graph (no edges) is trivial planar. Handle separately if your API requires a defined result.

Disconnected graphs: A graph is planar iff all its connected components are planar. Test each component and AND the results, or preprocess into components.

Undirected vs directed: Planarity is defined for undirected graphs. For directed graphs, ignore direction and test the underlying undirected graph.

Efficiency with Euler's formula: Always check E > 3V − 6 first. It is free and rejects many non-planar graphs instantly, saving the O(V+E) algorithm for borderline cases.

Dense graphs: For graphs with E ≥ 3V, Euler's formula alone might reject. For sparse graphs (E ≈ V), the full algorithm is necessary.

Witness/certificate: If you need to prove a graph is non-planar (e.g., for visualization or debugging), extract the Kuratowski obstruction. Boyer-Myrvold supports this directly; other algorithms require post-processing.

Kuratowski

G planar iff no subgraph is a subdivision of K₅ or K₃,₃. A subdivision replaces an edge with a path (inserting degree-2 vertices). Kuratowski's theorem (1930) is the foundational forbidden-pattern result for planarity: these two graphs, in any subdivision, are the only topological obstructions. Elegant theory, but detecting subdivisions directly is expensive; modern algorithms use different characterizations for speed.

Wagner

Equivalent: no minor is K₅ or K₃,₃. A graph minor is obtained by deleting or contracting edges. Wagner's formulation (1937) replaces "subdivisions" with "minors," yielding the same characterization. Minors are more general (every subdivision is a minor, but not vice versa), yet both theorems describe the same planar/non-planar boundary. The minor perspective opened doors to Robertson-Seymour theory; algorithmically, both subdivisions and minors are expensive to check directly, so algorithms use constructive proof (DFS-based) instead.

Hopcroft-Tarjan

O(V+E) via DFS + path addition. The landmark 1974 algorithm by Hopcroft and Tarjan. Build a DFS spanning tree, then iteratively add back-edges (non-tree edges). For each back-edge (u,v), the unique path in the tree from u to v divides the plane. Test for conflicts (nested paths that would force a crossing) using clever interval data structures on the DFS stack. If no conflicts, the graph is planar; if a conflict arises, report non-planarity. Complex to implement correctly due to DFS-stack bookkeeping, but guaranteed linear time. Most modern libraries use Boyer-Myrvold instead for simplicity.