How Planarity Testing Algorithm Works: Deep Dive with Code

1. Introduction and Core Concepts

A planarity testing algorithm determines whether a given undirected graph can be drawn on a plane without any edges crossing. A graph that admits such a drawing is called planar, while a graph that inevitably requires at least one crossing is non-planar. This property is far more than a mathematical curiosity; it fundamentally constrains how networks, circuits, and layouts can be physically realized.

The theoretical foundation for the planarity testing algorithm rests on two classic results. First, Euler's formula for connected planar graphs states that for any planar embedding with n vertices, m edges, and f faces, n - m + f = 2. This leads to a crucial necessary condition for simple planar graphs with n >= 3: m <= 3n - 6. If a graph violates this inequality, it is immediately non-planar. Second, Kuratowski's Theorem characterizes planarity by forbidden subdivisions: a graph is planar if and only if it contains no subdivision of K5 (the complete graph on five vertices) or K3,3 (the complete bipartite graph with three vertices in each partition). Wagner's theorem provides an equivalent characterization via graph minors.

Why does the planarity testing algorithm matter in computer science? Many problems that are NP-hard on general graphs become tractable on planar graphs. For example, the Four Color Theorem guarantees that every planar graph is 4-colorable, and there are linear-time algorithms for 3-colorability testing and efficient approximation schemes for maximum independent set, traveling salesman, and other optimization problems on planar graphs. Before applying these specialized algorithms, we must first verify planarity. Furthermore, planar embeddings are essential for graph drawing, VLSI layout, and visualization, where edge crossings directly translate to wire crossings, visual clutter, or increased manufacturing cost.

What Defines a Planar Embedding?

A planar embedding is not just a yes/no answer; it is a specific combinatorial structure that describes the cyclic order of edges around each vertex and the set of faces. A robust planarity testing algorithm typically does more than return a boolean — it either produces a planar embedding (a rotation system) or provides a Kuratowski subgraph as a certificate of non-planarity. This certificate is invaluable for debugging and for algorithms that need to handle non-planar inputs gracefully.

Early approaches to the planarity testing algorithm were exponential, enumerating all possible embeddings or searching for Kuratowski subdivisions by brute force. The breakthrough came in 1974 when John Hopcroft and Robert Tarjan proved that planarity could be tested in linear time, O(n + m), which is asymptotically optimal since any algorithm must examine the entire graph. Modern linear-time algorithms, most notably the Boyer-Myrvold algorithm, are simpler to implement and form the basis of libraries like OGDF, NetworkX, and the Boost Graph Library.

2. How It Works

At a high level, every efficient planarity testing algorithm exploits depth-first search (DFS) to impose structure on the graph. The DFS tree partitions edges into tree edges and back edges, creating a set of fundamental cycles. The core challenge is to determine whether these cycles can be arranged around the DFS tree without forcing a crossing. Different algorithms solve this arrangement problem with different data structures.

The Hopcroft-Tarjan algorithm, the first linear-time method, uses the concept of path decomposition. It decomposes the graph into a set of paths (called segments) that are added back to the DFS tree one by one. Each path has two endpoints on the already-embedded portion. The algorithm maintains a data structure representing the possible permutations of embedded segments that can be flipped to accommodate new paths. This is managed using a stack of blocks and careful bookkeeping of lowpoints — the lowest discovery time reachable from a subtree via back edges. If at any point a path cannot be embedded on either side of its parent path without crossing, the graph is non-planar.

The Boyer-Myrvold algorithm, which has largely superseded Hopcroft-Tarjan in practice due to its simplicity, reframes the problem as a left-right partition problem. During a DFS, it attempts to assign each back edge to either the left or right side of its DFS tree path. The constraint is that two back edges that interlace or overlap in a way that forces a K3,3 or K5 structure cannot be placed on the same side. This is modeled as a 2-coloring problem on a conflict graph of back edges. The algorithm uses a structure of bicomps (biconnected components) with flip bits to efficiently represent and test these constraints in amortized constant time.

DFS Tree and Lowpoints

Both major algorithms rely heavily on DFS numbering and lowpoint values. For each vertex v, disc[v] is its discovery time, and low[v] = min({disc[v]} ∪ {disc[w] | there exists a back edge (u, w) where u is in the subtree of v}). The lowpoint indicates how high up the DFS tree the subtree of v can reach. Vertices with lowpoints that interleave are precisely those that create embedding conflicts. Understanding this DFS scaffolding is essential for implementing any linear-time planarity testing algorithm correctly.

From Testing to Embedding

A complete planarity testing algorithm does not stop at a boolean result. If the graph is planar, it constructs an explicit embedding by ordering adjacency lists according to the left/right assignments or stack decisions. This embedding can then be used to enumerate faces, construct the dual graph, or produce straight-line coordinates via algorithms like Schnyder's or Tutte's. If the graph is non-planar, a modern implementation will extract a Kuratowski subdivision — a set of paths that form a K5 or K3,3 — which serves as a verifiable proof of non-planarity.

3. Implementation

Implementing a full linear-time planarity testing algorithm from scratch is a substantial undertaking. Below we present a progression from a simple, educational filter to a more faithful linear-time core. The first snippet implements the fast Euler bound check and a naive Kuratowski search for small graphs, which is useful as a pre-filter.

def euler_planarity_filter(n, m, is_simple=True):
    """
    Fast necessary condition for planarity using Euler's formula.
    Returns False if definitely non-planar, None if inconclusive.
    For simple graphs with n >= 3: m <= 3*n - 6 must hold.
    For triangle-free graphs: m <= 2*n - 4.
    """
    if n < 3:
        return None  # K1, K2 are planar
    if is_simple and m > 3 * n - 6:
        return False  # Violates Euler -> non-planar
    # For bipartite/triangle-free graphs, tighter bound applies
    # if is_triangle_free and m > 2 * n - 4:
    #     return False
    return None  # Need deeper test

def is_planar_bruteforce_small(n, edges):
    """
    Brute-force Kuratowski check for n <= 8 by testing all subdivisions.
    Educational only - exponential time. For larger n use DFS method.
    """
    import itertools
    if euler_planarity_filter(n, len(edges)) is False:
        return False
    # For very small graphs, check for K5 or K3,3 as subgraphs
    # (full subdivision check is more complex)
    vertices = list(range(n))
    # Check K5
    if n >= 5:
        for subset in itertools.combinations(vertices, 5):
            needed = 10  # edges in K5
            count = sum(1 for u, v in edges if u in subset and v in subset)
            if count >= 10:
                # Found K5 (or dense enough to need subdivision check)
                pass
    return None

The second snippet shows the DFS and lowpoint computation that underpins every linear-time planarity testing algorithm. Getting lowpoints correct, including handling parent edge and parallel edges, is the most common source of bugs.

def compute_dfs_lowpoints(adj, n):
    """
    Compute discovery times and lowpoints for planarity testing.
    adj: adjacency list, adj[u] = list of neighbors
    Returns disc, low, parent, dfs_order
    """
    disc = [-1] * n
    low = [0] * n
    parent = [-1] * n
    time = 0
    stack = [(0, 0, iter(adj[0]))]  # (node, iterator state)
    
    # Iterative DFS to avoid recursion limits
    disc[0] = low[0] = time
    time += 1
    parent_stack = [0]
    
    order = []
    visited = [False] * n
    visited[0] = True
    
    # Use explicit stack for full DFS
    sys_stack = [(0, 0)]  # (node, next neighbor index)
    parent[0] = -1
    
    while sys_stack:
        u, idx = sys_stack[-1]
        if idx < len(adj[u]):
            v = adj[u][idx]
            sys_stack[-1] = (u, idx + 1)
            if not visited[v]:
                visited[v] = True
                disc[v] = low[v] = time
                time += 1
                parent[v] = u
                order.append((u, v))  # tree edge
                sys_stack.append((v, 0))
            elif v != parent[u] and disc[v] < disc[u]:
                # Back edge (u, v) where v is ancestor
                # Update low for u
                if disc[v] < low[u]:
                    low[u] = disc[v]
        else:
            # Finish node u, propagate low to parent
            p = parent[u]
            if p != -1:
                # low[p] = min(low[p], low[u])
                if low[u] < low[p]:
                    low[p] = low[u]
            sys_stack.pop()
    
    return disc, low, parent, order

The third snippet sketches the core loop of the Boyer-Myrvold left-right planarity testing algorithm. This is simplified for clarity; a production version requires bicomp merging and efficient conflict handling with a stack of intervals.

def boyer_myrvold_planarity_test(adj, n):
    """
    Simplified Boyer-Myrvold planarity testing algorithm.
    Attempts to assign each back edge to LEFT or RIGHT.
    Returns (is_planar, embedding or kuratowski_subgraph)
    """
    disc, low, parent, _ = compute_dfs_lowpoints(adj, n)
    # Sort adjacency by DFS order (lowpoint ordering)
    # This ordering is critical for linear time
    for u in range(n):
        adj[u].sort(key=lambda v: disc[v] if disc[v] != -1 else float('inf'))
    
    # Stack of bicomps: each bicomp has left/right intervals and flip flag
    bicomps = []  # In full impl: list of objects with ref stack
    is_planar = True
    
    # Process vertices in reverse DFS order (bottom-up)
    vertices_by_disc = sorted(range(n), key=lambda x: disc[x], reverse=True)
    
    for v in vertices_by_disc:
        # Merge bicomps of children where low[child] < disc[v]
        # Check for conflicts: two back edges (v, a) and (v, b) that interlace
        # must be on opposite sides if they overlap in embedding
        for w in adj[v]:
            if parent[w] == v:
                # Tree edge v -> w, handle bicomp of w
                pass
            elif disc[w] < disc[v]:
                # Back edge v -> w (w is ancestor)
                # Try to place on left or right
                # Conflict check: if w is inside a bicomp that already has
                # edges on both sides, embedding fails
                pass
        if not is_planar:
            break
    
    # Full implementation would return embedding as rotation system:
    # embedding[v] = cyclic order of neighbors around v
    return is_planar, None

The final snippet demonstrates how to use a mature library for production use while also extracting an embedding for graph drawing. This is the recommended approach for most applications unless you are building a specialized graph library.

def planarity_with_networkx(n, edge_list):
    """
    Production-ready planarity testing using NetworkX's
    Boyer-Myrvold implementation (linear time).
    Also extracts planar embedding if it exists.
    """
    import networkx as nx
    
    G = nx.Graph()
    G.add_nodes_from(range(n))
    G.add_edges_from(edge_list)
    
    # NetworkX implements Boyer-Myrvold internally
    is_planar, embedding = nx.check_planarity(G, counterexample=False)
    
    if is_planar:
        # embedding is a PlanarEmbedding object
        # Get cyclic order around each node
        rotation_system = {}
        for v in range(n):
            # embedding.neighbors_cw_order(v) gives clockwise order
            try:
                order = list(embedding.neighbors_cw_order(v))
                rotation_system[v] = order
            except Exception:
                rotation_system[v] = list(G.neighbors(v))
        return True, rotation_system
    else:
        # Optionally get Kuratowski subgraph as certificate
        is_planar2, certificate = nx.check_planarity(G, counterexample=True)
        # certificate is a subgraph that is a K5 or K3,3 subdivision
        return False, certificate

# Example: K3,3 is non-planar, cube graph is planar
cube_edges = [(0,1),(1,2),(2,3),(3,0),(4,5),(5,6),(6,7),(7,4),(0,4),(1,5),(2,6),(3,7)]
print(planarity_with_networkx(8, cube_edges)[0])  # True

k33_edges = [(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)]
print(planarity_with_networkx(6, k33_edges)[0])  # False

4. Step-by-Step Example

Let us walk through the planarity testing algorithm on two concrete graphs: a planar 4-vertex graph with a diagonal, and the non-planar K3,3. This walkthrough illustrates how the DFS structure exposes conflicts.

Consider Graph A: vertices {0,1,2,3} with edges (0-1, 1-2, 2-3, 3-0, 0-2). This is a 4-cycle with one diagonal, clearly planar. Run DFS from 0: suppose the DFS tree is 0 -> 1 -> 2 -> 3. Tree edges are (0,1), (1,2), (2,3). Back edges are (3,0) and (0,2). Discovery times are disc[0]=0, disc[1]=1, disc[2]=2, disc[3]=3. Lowpoints: low[3]=0 via back edge (3,0), low[2]=0 (min of disc[2] and low[3]), low[1]=0, low[0]=0.

The algorithm processes vertices bottom-up. At vertex 3, back edge (3,0) must be embedded. It can be placed on either side, say LEFT. At vertex 2, back edge (0,2) is encountered. Its endpoints are 0 and 2, which are already connected by the tree path 0-1-2. The existing back edge (3,0) uses the path 0-1-2-3. These two back edges do not interlace in a way that forces a crossing; they can be placed on opposite sides or even the same side by nesting. The Boyer-Myrvold test finds no conflict, merging bicomps successfully, and declares the graph planar. The resulting embedding might order neighbors of 0 as [1,2,3] clockwise.

Walkthrough on K3,3 (Non-Planar)

Now consider Graph B: K3,3 with partitions {0,1,2} and {3,4,5} and all 9 cross edges. Run DFS from 0: one possible DFS tree is 0-3-1-4-2-5. Tree edges: (0,3), (3,1), (1,4), (4,2), (2,5). Back edges: (0,4), (0,5), (1,3 is tree but 1-5, 2-3, etc.). More systematically, after DFS, every non-tree edge connects a vertex to an ancestor.

When processing bottom-up, the algorithm encounters multiple back edges that all need to be routed around the long DFS path. For instance, edges (0,4) and (1,5) interlace: their endpoints alternate along the DFS path order. In the left-right model, this means they cannot be assigned to the same side. As more back edges are processed, the conflict graph becomes non-bipartite — it requires three colors where only two (LEFT/RIGHT) are available. At the point where vertex 0 is processed, the stack of bicomps contains intervals that overlap on both sides simultaneously. The algorithm detects that no flip assignment can resolve the overlap, triggers a failure, and can trace back the set of edges forming a K3,3 subdivision as a certificate.

This step-by-step merging and conflict detection is why the ordering of adjacency lists by lowpoint is critical. Without it, the algorithm would need to scan arbitrarily many intervals, leading to quadratic time. With proper ordering, each edge is pushed and popped from the bicomp stack at most once, yielding linear time.

5. Complexity Analysis

The complexity of the planarity testing algorithm depends dramatically on the approach chosen. Naive methods are exponential, while the optimal linear-time algorithms are theoretically and practically efficient. Understanding these trade-offs is essential for selecting the right implementation for your graph size and requirements.

The Euler filter is O(1) after counting edges and provides an instant rejection for dense non-planar graphs. The brute-force Kuratowski search is O(n! ) in the worst case and only feasible for n < 10. The Hopcroft-Tarjan and Boyer-Myrvold algorithms both achieve O(n + m) time and O(n + m) space, which is optimal. However, their constant factors and implementation complexity differ significantly.

Space complexity is often overlooked. All linear-time algorithms require O(n + m) additional memory for DFS stacks, lowpoints, parent pointers, and the bicomp/block stack. For very large graphs (millions of vertices), memory locality and iterative DFS (to avoid recursion depth limits) become important. An iterative implementation may use slightly more memory for an explicit stack but avoids Python recursion limits and stack overflow in C++.

In practice, the Boyer-Myrvold algorithm is about 20-30% faster than Hopcroft-Tarjan due to simpler data structures and better cache behavior. For sparse planar graphs where m = O(n), the entire test runs in O(n) time. For dense graphs that fail the Euler test early, the effective time is O(1). When benchmarking, always measure both planar and non-planar inputs, as early exit paths can skew results.

6. Variations and Optimizations

While the core linear-time planarity testing algorithm is optimal asymptotically, several variations and optimizations address practical concerns such as simplicity, certificate generation, and handling of disconnected or non-simple graphs.

The Left-Right Planarity Test is a modern simplification of Boyer-Myrvold that is particularly amenable to teaching and implementation. It explicitly maintains for each vertex a set of constraints that two back edges must be on different sides, encoded as intervals on a stack. Its correctness proof is more accessible than the original Hopcroft-Tarjan, and it naturally produces an embedding without a separate phase. Many recent textbooks present this variant as the canonical linear-time algorithm.

Another important variation is incremental planarity testing, where edges are added one by one and the algorithm must maintain planarity dynamically. Fully dynamic planarity (with edge deletions) is much harder, with known polylogarithmic algorithms that are complex to implement. For offline batch processing, however, simply re-running Boyer-Myrvold after each batch is often sufficient.

Optimizations for real implementations include: using iterative DFS to avoid recursion limits, sorting adjacency lists by lowpoint using bucket sort (counting sort) to achieve true O(n + m) rather than O(m log m), using adjacency compression for dense graphs, and early exit on finding a Kuratowski subdivision to avoid unnecessary work. For graphs with multiple components, test each component separately — a graph is planar iff every component is planar.

For handling non-simple graphs, note that loops make a graph non-planar in the usual definition, while parallel edges (multi-graphs) can be reduced: a graph with parallel edges is planar iff its underlying simple graph is planar, except that two parallel edges already form a cycle that may affect embedding. Most libraries first simplify the graph by removing loops and deduplicating edges.

7. Real-World Applications

Planarity testing may seem abstract, but it underpins several critical systems where edge crossings have physical or performance consequences. Recognizing when a problem reduces to planarity can unlock efficient algorithms and better designs.

In VLSI and PCB design, the planarity testing algorithm determines whether a circuit can be laid out on a single layer without wire crossings. A planar circuit requires only one layer, reducing manufacturing cost and signal interference. When the circuit is non-planar, the size of the minimum Kuratowski subdivision estimates how many vias (layer transitions) or how many layers are needed. Modern chip design tools run planarity tests on subcircuits thousands of times during floorplanning.

In network visualization and graph drawing, planar embeddings produce the most readable layouts. Tools like Graphviz, yEd, and D3.js use planarity testing to decide whether to apply a planar straight-line drawing algorithm (e.g., Schnyder woods) or to fall back to force-directed methods that minimize crossings. For road networks, which are often nearly planar, testing planarity helps validate map data — an unexpected K3,3 might indicate a data error such as a missing bridge or tunnel annotation.

In software engineering, planarity appears in dependency graphs and database query optimization. Some efficient algorithms for planar graphs, such as linear-time single-source shortest paths without Dijkstra's overhead or subexponential parameterized algorithms, are applicable when the dependency graph of a build system or the join graph of a query is planar. Web infrastructure also benefits: the topology of certain content delivery networks and the layout of data center interconnects are designed to be planar to simplify routing.

Beyond these, planarity testing is a subroutine in more advanced algorithms: testing if a graph has a planar embedding with additional constraints (e.g., fixed outer face), computing the crossing number, and approximating the genus of a graph. In each case, the linear-time test serves as the base case or fast path.

8. Comparison with Alternatives

Choosing the right planarity testing algorithm depends on graph size, need for embedding, implementation effort, and language constraints. The table below compares the major approaches, including naive alternatives that are sometimes mistakenly used in practice.

For production code, the Boyer-Myrvold algorithm as implemented in established libraries is almost always the correct choice. It is linear, provides embeddings and certificates, and has been extensively tested. Implementing Hopcroft-Tarjan from scratch is rarely justified today except for educational purposes. Brute-force methods should be limited to tiny graphs or as a correctness oracle for testing your linear implementation on random small graphs.

An alternative family of algorithms uses the concept of PQ-trees, introduced by Booth and Lueker. PQ-trees represent all permissible permutations of edges around vertices and can test planarity in linear time while also solving related problems like consecutive ones. While elegant, PQ-trees are more complex to implement correctly than Boyer-Myrvold and have larger constant factors, so they are less common in modern libraries.

If you cannot use an external library, consider implementing the Left-Right algorithm, which is essentially a clean reformulation of Boyer-Myrvold. It requires only arrays, stacks, and DFS, without the complex block structures of Hopcroft-Tarjan. Several open-source Python implementations of Left-Right are available in under 300 lines and are suitable for interview or academic projects.

9. Common Mistakes and Best Practices

Implementing a planarity testing algorithm is notoriously error-prone. Even published implementations have contained subtle bugs that only surface on specific non-planar graphs. Awareness of common pitfalls can save weeks of debugging.

The most frequent mistake is incorrect handling of lowpoints and parent edges. When computing low[v], you must consider only back edges to ancestors, not the edge to the parent in the DFS tree. Failing to exclude the parent edge causes low values to be artificially low, masking conflicts and incorrectly declaring non-planar graphs as planar. Similarly, parallel edges must be treated as a cycle of length 2; if you deduplicate edges before DFS, you may incorrectly declare a multi-graph planar when its underlying simple graph is planar but the multi-graph requires special handling.

Another common error is using recursive DFS in Python or Java without accounting for recursion depth. A path graph with 10,000 vertices will exceed Python's default recursion limit of 1000, causing a crash. Always implement DFS iteratively for production code or increase the recursion limit and use sys.setrecursionlimit. Additionally, sorting adjacency lists by discovery time using a standard O(m log m) sort breaks the linear-time guarantee; while this is acceptable for moderate graphs, true linear time requires bucket sort by lowpoint.

Best practices include: always run the Euler filter first; test each connected component separately; use an existing library (NetworkX, OGDF, Boost) for production; when implementing from scratch, validate against a brute-force oracle on thousands of random small graphs (n <= 9) where brute force is feasible; and ensure your algorithm returns a certificate (embedding or Kuratowski subgraph) rather than just a boolean, as this makes testing and debugging far easier. Finally, remember that planarity is defined for undirected graphs — if your input is directed, consider its underlying undirected version.

Checklist for Robust Implementation

• Handle disconnected graphs by testing each component.
• Remove self-loops upfront; they immediately imply non-planarity for simple embeddings.
• Use iterative DFS and bucket sort for linear time.
• Exclude parent edge when computing lowpoints.
• Generate and verify embedding or Kuratowski certificate in tests.
• Benchmark on both sparse planar and dense non-planar graphs.

10. Interview Questions

Planarity testing is a favorite topic for advanced algorithms interviews, especially for roles involving graph algorithms, networks, or visualization. Interviewers often probe both theoretical understanding and practical implementation trade-offs.

Q1: How would you quickly determine that a graph is definitely non-planar without running a full planarity test?

Answer: Apply Euler's formula as a necessary condition. For a simple connected planar graph with n >= 3, m <= 3n - 6. If m > 3n - 6, the graph is non-planar. For triangle-free (e.g., bipartite) graphs, the tighter bound m <= 2n - 4 applies. For example, K5 has n=5, m=10, and 3n-6=9, so 10 > 9 proves non-planarity instantly. Similarly, K3,3 has n=6, m=9, and since it is bipartite, 2n-4=8, so 9 > 8 proves non-planarity. This O(1) check should always be the first step before invoking a linear-time algorithm.

Q2: What is Kuratowski's Theorem and how does it relate to the planarity testing algorithm?

Answer: Kuratowski's Theorem states that a graph is planar iff it contains no subdivision of K5 or K3,3. A subdivision is obtained by replacing edges with paths. While this characterization is elegant, directly searching for such subdivisions is exponential. Efficient planarity testing algorithms like Hopcroft-Tarjan and Boyer-Myrvold implicitly search for these structures in linear time via DFS and left-right constraints. When they declare a graph non-planar, they can often extract the Kuratowski subdivision as a certificate, providing a constructive proof of the theorem.

Q3: Explain why Hopcroft-Tarjan and Boyer-Myrvold achieve O(n + m) time. What is the key insight?

Answer: The key insight is to use DFS to impose a linear order and then process vertices bottom-up, maintaining embedding possibilities with a stack that supports amortized O(1) operations per edge. The DFS tree defines parent-child relationships and lowpoints, which determine the order in which adjacency lists are processed. By sorting adjacency lists by lowpoint (using bucket sort) and using a stack of bicomps/blocks where each edge is pushed and popped at most once, the total work is linear. Without this ordering, the algorithm would need to scan many intervals per edge, leading to O(n^2) time.

Q4: Given a planar graph, how would you produce an actual drawing without edge crossings?

Answer: First run a planarity testing algorithm that returns a planar embedding (rotation system). Then apply a planar drawing algorithm: for a straight-line embedding, use Schnyder's algorithm (which embeds an n-vertex planar graph on an (n-2) x (n-2) grid) or Tutte's barycentric embedding (which fixes the outer face and places each interior vertex at the centroid of its neighbors). For orthogonal drawings (common in VLSI), use Tamassia's algorithm. The embedding from the planarity test is essential because it defines the face structure that these drawing algorithms require.

Q5: How would you test planarity for a graph with 10 million vertices in Python?

Answer: A pure Python implementation of Boyer-Myrvold would be too slow and memory-heavy for 10 million vertices. Best practices: 1) Use the Euler filter to quickly reject dense graphs. 2) Process each connected component separately and in parallel. 3) Use a highly optimized C/C++ library like OGDF or the Boost Graph Library via Python bindings, or use NetworkX's C-optimized check_planarity if available. 4) Ensure iterative DFS to avoid recursion limits and use compressed adjacency representations (arrays of ints). 5) If only a yes/no answer is needed, consider streaming or external-memory algorithms. For most interviews, acknowledging the need to move beyond pure Python for this scale demonstrates systems awareness.