Linear-Time Planarity Testing

From Euler’s Formula to Linear-Time Testing

Euler supplied the first numerical invariant of a crossing-free drawing. Kuratowski later identified the two unavoidable topological obstructions, and Hopcroft and Tarjan showed that planarity can be decided in linear time. The modern problem is richer than a yes/no test: when a graph is planar, we want an embedding; when it is not, we often want a compact witness.

A Crossed Drawing Is Not a Nonplanarity Proof

A graph is planar if it has some drawing in the plane where edges meet only at common endpoints. A plane graph is a planar graph together with one particular crossing-free embedding.

Euler’s Formula Gives Fast Rejection Bounds

For a connected plane graph, with $n$ vertices, $m$ edges, and $f$ faces including the outer face:

In a simple planar graph with $n\ge3$, each face boundary has length at least $3$, while every edge borders two face-sides. Thus $3f\le2m$. Combining the inequalities with Euler’s formula gives:

If the graph is bipartite, it has no odd cycle, so every face has length at least $4$ and the stronger bound is:

The Two Shapes Behind Every Nonplanar Graph

$K_5$ connects every pair of five vertices. $K_{3,3}$ connects each of three left vertices to each of three right vertices. Neither is planar.

A subdivision replaces an edge with a path by inserting degree-2 vertices. Suppressing those degree-2 vertices recovers the original obstruction. This explains why edge-density bounds are incomplete: subdivisions make a graph larger and sparser without making it planar.

What a Linear-Time Tester Actually Does

Production algorithms differ in their data structures, but the shared logic is to expose how non-tree edges must attach around a DFS skeleton and check whether all left/right placement constraints can be satisfied.

flowchart TD
    G[Normalize graph and split components] --> B[Process biconnected blocks]
    B --> D[Build DFS tree and lowpoint data]
    D --> C[Propagate embedding constraints]
    C --> Q{Constraints consistent?}
    Q -->|Yes| P[Return planar rotation system]
    Q -->|No| K[Return Kuratowski witness]

1. Normalize: handle isolated vertices, components, self-loops, and parallel edges according to the library’s contract.
2. Decompose: planarity can be checked block by block because articulation vertices can join planar pieces.
3. Search: a DFS tree orders ancestor paths; lowpoint information summarizes how subtrees reconnect upward.
4. Constrain: back-edge attachments must be placed consistently on the two sides of partial embeddings.
5. Certify: produce a rotation system or extract a $K_5/K_{3,3}$ subdivision.

The Real Positive Output: A Rotation System

A combinatorial embedding records the cyclic order of incident edges around every vertex. This rotation system determines how edges thread through the plane without committing to screen coordinates.

For simple planar graphs, Fáry’s theorem guarantees that some crossing-free straight-line drawing exists. The planarity tester usually supplies the topology first; a planar drawing algorithm then chooses coordinates and visual spacing.

Implement the Safe Prechecks; Reuse the Full Tester

Density checks are simple and valuable, but their return type should communicate definite rejection, not planarity. The snippets assume a simple graph.

def rejected_by_density(vertices, edges, bipartite=False):
    if vertices < 3:
        return False
    limit = 2 * vertices - 4 if bipartite else 3 * vertices - 6
    return edges > limit

print(rejected_by_density(5, 10))        # True: rejects K5
print(rejected_by_density(6, 9))         # False: K3,3 remains unknown
print(rejected_by_density(6, 9, True))   # True: bipartite bound rejects it

bool rejectedByDensity(long long vertices, long long edges,
                       bool bipartite = false) {
    if (vertices < 3) return false;
    long long limit = bipartite
        ? 2 * vertices - 4
        : 3 * vertices - 6;
    return edges > limit;
}

// false means “unknown,” never “proved planar”
bool k33General = rejectedByDensity(6, 9);       // false
bool k33Bipartite = rejectedByDensity(6, 9, true); // true

static boolean rejectedByDensity(long vertices, long edges,
                                 boolean bipartite) {
    if (vertices < 3) return false;
    long limit = bipartite
        ? 2 * vertices - 4
        : 3 * vertices - 6;
    return edges > limit;
}

// false means “unknown,” never “proved planar”
boolean k33General = rejectedByDensity(6, 9, false); // false
boolean k33Bipartite = rejectedByDensity(6, 9, true); // true

Worked Examples: What Each Check Can Prove

The final row is the important one: adding degree-2 vertices dilutes density while preserving the obstruction. No edge-count inequality can replace the structural test.

Where Planarity Testing Pays Off

Common Misreadings and Boundary Cases

Complexity and Choosing the Right Tool

Hopcroft–Tarjan, Boyer–Myrvold, and other established approaches run in $O(n+m)$ time. The asymptotic result is elegant; the implementation details are subtle enough that a mature library is usually safer than a fresh production implementation.