Hopcroft-Tarjan Planarity Algorithm

Purpose: Decide whether a graph is planar — drawable in the plane with no edge crossings — in $O(V)$ time. The first linear-time planarity test (1974).

Preliminaries

By Euler’s formula $V-E+F=2$, a simple planar graph satisfies $E\le 3V-6$ (and $E\le 2V-4$ if bipartite/triangle-free). So the first line of any planarity test is:

if (E > 3 * V - 6) return false;   // not planar, and now everything is O(V)

This is why the complexity is stated in $V$ alone.

By Kuratowski’s theorem, a graph is planar iff it contains no subdivision of $K_5$ or $K_{3,3}$. Testing that directly is hopeless; the algorithms below take structural routes instead.

The path addition method

1. Reduce to a biconnected graph (planarity is testable per biconnected component, see biconnected components).
2. Find a cycle $C$; the rest of the graph decomposes into bridges (pieces attached to $C$).
3. Embed $C$, then add the remaining pieces one path at a time, deciding for each whether it goes inside or outside the cycle.
4. The inside/outside choices interact: two pieces “conflict” if they interleave on the cycle and cannot both go on the same side. Build a conflict graph and test it for 2-colourability — this is exactly 2-SAT / bipartiteness.
5. Hopcroft and Tarjan use a DFS with careful ordering so that the conflicts can be resolved with a stack in linear time, rather than building the conflict graph explicitly.

Complexity

• Time: $O(V)$
• Space: $O(V)$
• Reputation: notoriously difficult to implement correctly — the original paper’s presentation is famously terse

The alternatives

Method	Time	Difficulty	Produces an embedding?
$E>3V-6$ check	$O(1)$	trivial	rejects only
Hopcroft-Tarjan (path addition)	$O(V)$	very hard	yes
Lempel-Even-Cederbaum + PQ-trees	$O(V)$	hard	yes
Boyer-Myrvold (edge addition)	$O(V)$	moderate	yes, plus Kuratowski subgraph
de Fraysseix-Rosenstiehl (left-right)	$O(V)$	moderate	yes

If you need this

Use Boyer-Myrvold or the left-right criterion. Both are substantially easier than Hopcroft-Tarjan, and Boyer-Myrvold additionally extracts an explicit $K_5$/$K_{3,3}$ subdivision when the graph is not planar — useful for constructive problems.

Where planarity shows up in contests

Rarely as an explicit test. More often you are told the graph is planar and expected to exploit it:

• planar graphs are 4-colourable (and 5-colourable constructively in linear time);
• they have $O(V)$ edges, so $O(E)$ becomes $O(V)$;
• they have $O(\sqrt{V})$ separators (Lipton-Tarjan), enabling divide and conquer;
• max flow in planar graphs has $O(n\log n)$ algorithms via duality — a min cut in the primal is a shortest cycle in the dual.

Variants / Use Cases

• Boyer-Myrvold — the implementable modern choice
• Tarjan’s biconnected components — the required preprocessing
• Planar separator theorem — the algorithmic payoff of planarity
• Graph drawing — Tutte’s spring embedding, Schnyder woods for straight-line grid drawings