Can a graph be drawn in the plane without edges crossing? A planarity testing algorithm answers that question; efficient versions can also produce a planar embedding. This is different from finding a drawing with the fewest crossings when the graph is non-planar. section 15.2.5 section 15.3.1
Before running an expensive test, reduce the work:
- For a simple, connected graph with at least three vertices, reject it if |E| > 3|V| − 6. If it has more than three vertices and no triangle, also reject it if |E| > 2|V| − 4. Passing these checks does not prove planarity. section 15.2.2
- Test connected components separately—or biconnected components for a finer split. A graph is planar exactly when every component tested this way is planar. Connected components can be found with DFS; biconnected components require a modified DFS. section 15.2.2 section 15.2.3
Listing 15.1 Planarity testing template algorithm
function planarityTesting(graph, isPlanar) #1
components ← biconnectedComponents(graph) #2
for G in components do #3
if not isPlanar(G) then #4
return false
return true #5
The template delegates the actual planarity decision to an `isPlanar` function and returns false as soon as one biconnected component fails. section 15.2.3
A straightforward recursive approach uses Kuratowski’s theorem: stop on graphs with fewer than five vertices, apply the Euler filters, check for the named non-planar graphs K5 and K3,3, then recursively examine subgraphs formed by removing each vertex or each edge. It is easier to write than the efficient alternatives, but its branching recursion makes it suitable only for small graphs. section 15.2.3 section 15.2.4
Listing 15.2 Planarity testing based on KK’s theorem
function isPlanar(graph)
if |graph.vertices| < 5 then return true #1
if violatesEulerConstraints(graph) then return false #2
if isK5(graph) or isK3_3(graph) then return false #3
for v in graph.vertices do #4
subG ← graph.remove(v) #5
if not isPlanar(subG) then return false #6
for e in graph.edges do #7
subG ← graph.remove(e) #8
if not isPlanar(subG) return false #9
return true #10
The pseudocode shows the early exits and both deletion loops that drive the recursive test. section 15.2.3
Those loops repeatedly reach the same subgraphs by different deletion orders. Caching results avoids some repeated tests, but the cached version remains too slow for large graphs. Linear-time algorithms instead use more involved strategies; the Hopcroft–Tarjan approach incrementally adds vertices while maintaining possible planar embeddings. Implementing such algorithms is a substantial trade-off against the simpler small-graph approach. section 15.2.4 section 15.2.5
