Boyer-Myrvold Planarity Algorithm

Purpose: Test planarity in $O(V)$ time, produce a planar embedding when the graph is planar, and extract an explicit $K_5$ or $K_{3,3}$ subdivision when it is not. The most implementable of the linear-time planarity algorithms (2004), and the one used by Boost Graph Library and networkx.

The Idea: edge addition

Where Hopcroft-Tarjan adds paths, Boyer-Myrvold adds edges, one at a time, keeping a valid embedding of what has been processed so far.

1. DFS the graph, recording a DFS tree with preorder numbers, lowpoint values, and the back edges out of each subtree.
2. Process vertices in reverse DFS order. When at vertex $v$, embed all back edges from descendants of $v$ up to $v$.
3. Maintain the partial embedding as a set of biconnected components (“bicomps”), each stored as a circular list of its external face. Crucially, a bicomp can be flipped in $O(1)$ — the orientation is stored lazily and resolved at the end.
4. To embed a back edge, walk the external face from the descendant up to $v$, merging bicomps along the way. Flipping is what lets the walk always proceed in one direction.
5. If a required vertex is not reachable on the external face, the graph is not planar — and the obstruction found at that moment is exactly a Kuratowski subgraph, which the algorithm then extracts in linear time.

Complexity

• Time: $O(V)$ (after the $E\le 3V-6$ early rejection makes $E=O(V)$)
• Space: $O(V)$
• Implementation: hundreds of lines, but the concepts are tractable — unlike PQ-trees or Hopcroft-Tarjan’s path stack

What makes it practical

1. $O(1)$ flipping. Storing orientation lazily removes the need to reverse lists, which is where naive edge-addition approaches become quadratic.
2. External-face walking. All the geometry reduces to walking a circular list, with no PQ-tree bookkeeping.
3. Kuratowski extraction for free. The failure state directly identifies the five (or six) branch vertices of the obstruction.

Comparison

	Hopcroft-Tarjan	Lempel-Even-Cederbaum + PQ-tree	Boyer-Myrvold
Adds	paths	vertices (st-numbering)	edges
Aux structure	conflict stack	PQ-tree	bicomp lists
Kuratowski subgraph	hard	hard	built in
Used by real libraries	rarely	occasionally	yes (Boost, networkx)

Related planarity facts worth remembering

• $E\le 3V-6$ for simple planar graphs with $V\ge 3$; $E\le 2V-4$ if triangle-free
• Every planar graph has a vertex of degree $\le 5$ — the basis of linear-time 5-colouring
• Planar graphs are 4-colourable (Appel-Haken); deciding 3-colourability of a planar graph is still NP-complete
• Every planar graph has an $O(\sqrt{V})$ separator (Lipton-Tarjan), which gives $2^{O(\sqrt{V})}$ exact algorithms for many NP-hard problems restricted to planar inputs

Variants / Use Cases

• Planar embedding — needed for dual-graph constructions, face enumeration, and planar max flow
• Graph drawing — feed the embedding to Schnyder woods or Tutte’s algorithm to get coordinates
• Biconnected components — the decomposition the algorithm maintains
• Hopcroft-Tarjan — the historical first