Planarity Testing Algorithms

Graph Theory · Axiom Academy

LESSON Planarity Testing Algorithms Efficiently determining if a graph can be drawn without edge crossings Testing planarity might seem like it requires checking all possible embeddings, which could be exponential. However, Hopcroft and Tarjan (1974) proved that planarity testing can be done in linear time! 2. DFS-Based Approach Overview Modern planarity testing algorithms build on depth-first search (DFS) . The DFS tree provides a natural ordering of vertices and classifies edges into tree edges and back edges. The key observation: back edges must be drawn "around" the DFS tree, and planarity constraints limit where they can go. 3. Hopcroft-Tarjan Algorithm Idea The Hopcroft-Tarjan algorithm processes vertices in DFS post-order, maintaining information about which back edges must be drawn on the "left" or "right" side of the current path. 4. PQ-Trees and Path Addition Methods Alternative approaches use different data structures to maintain planarity constraints: Both approaches achieve O(n) time complexity through careful data structure design and incremental processing. Linear-time planarity testing has wide-ranging applications across computer science and engineering:

This is the written version of the interactive lesson above. See the full Graph Theory course.