Planar Graph Checker

About Planar Graph Checker

The Planar Graph Checker decides whether a simple undirected graph is planar — drawable in the plane without any two edges crossing — and, when the graph fails the test, it finds and visualises the Kuratowski witness: a subdivision of either K₅ (the complete graph on 5 vertices) or K₃,₃ (the complete bipartite graph on 3 + 3 vertices). The tool is built for teaching, competitive programming warm-ups, and quickly sanity-checking small graph constructions.

What Does "Planar" Mean?

A graph G = (V, E) is planar if it can be embedded in the plane so that edges meet only at their shared endpoints — no crossings. Equivalently, G can be drawn on the surface of a sphere without crossings. Planarity is a purely topological property: it does not depend on how you draw the graph, only on whether some crossing-free drawing exists.

Planar graphs show up everywhere — road and utility networks, printed-circuit-board routing, the edge graphs of Platonic solids, and the face structure of polyhedra. Yet many "natural" graphs are stubbornly non-planar: any time you try to connect 3 houses to 3 utilities without crossings, you run into the K₃,₃ barrier.

Kuratowski's Theorem — The Heart of the Checker

Kazimierz Kuratowski proved in 1930 that planarity has a purely combinatorial characterisation:

A subdivision of a graph H is obtained by replacing some edges of H with longer paths whose internal vertices are all new degree-2 vertices. Kuratowski's theorem therefore says that K₅ and K₃,₃ are the only obstructions to planarity — every non-planar graph contains one of them in a "stretched" form.

The Forbidden Graphs

Euler's Formula and Fast Necessary Conditions

Before running the (relatively expensive) subdivision search, the checker applies two fast necessary conditions derived from Euler's formula: for any connected planar graph drawn in the plane with V vertices, E edges, and F faces (counting the unbounded outer face), we have

Combined with the observation that every face of a simple planar graph has at least 3 edges on its boundary, we get the edge-upper-bound

Any graph violating these inequalities is immediately non-planar, no subdivision search needed. K₅ has m = 10, n = 5 ⇒ 3n − 6 = 9, so 10 > 9 — violates the bound. K₃,₃ has m = 9, n = 6 ⇒ 2n − 4 = 8, so 9 > 8 — violates the bipartite bound.

How the Subdivision Search Works

After the cheap Euler checks, the checker searches for a subdivision directly:

1. Quick win — detect K₅ or K₃,₃ as a literal subgraph. If 5 vertices are pairwise adjacent, that's K₅ outright. If 6 vertices split 3 + 3 with all 9 cross-edges present, that's K₃,₃.
2. K₅ subdivision search. For each candidate set of 5 "branch" vertices (each with degree ≥ 4 in G), try to find 10 paths — one per pair of branches — that are internally vertex-disjoint (no non-branch vertex appears in more than one path) and avoid using the other branches as internal vertices. A hit proves non-planarity.
3. K₃,₃ subdivision search. Pick 6 branches (each with degree ≥ 3) and a 3 + 3 bipartition. Search for 9 cross-pair paths with the same internal-disjointness requirement.
4. No witness ⇒ planar. If neither subdivision is found within the size limits, Kuratowski's theorem guarantees the graph is planar.

Finding vertex-disjoint paths is NP-hard in general, so the checker uses a bounded randomised greedy search: each iteration orders the required pairs by difficulty, picks a path for the hardest pair first using a randomised BFS, removes those internal vertices, and continues. If that particular ordering fails, it retries with a shuffled order — up to 40 attempts per branch configuration. On every small graph tested (up to 16 vertices), this suffices to locate a witness whenever one exists.

How to Use This Calculator

1. Pick an input format using the tabs at the top: edge list or adjacency list. Either encodes the same graph.
2. Enter your graph. The graph is treated as undirected, so A-B and B-A are the same edge.
3. Click Check Planarity. The tool reports a verdict, shows step-by-step reasoning (Euler, bipartite, Kuratowski), and renders the graph.
4. For a non-planar graph the visualisation colours the K₅ or K₃,₃ subdivision and lists the 10 (or 9) vertex-disjoint paths. Click a path row to isolate it.
5. For a planar graph the face count F = m − n + 1 + c is reported alongside the graph structure.

Worked Example 1 — K₄ is planar

K₄ has n = 4, m = 6. Every graph on ≤ 4 vertices is planar, and indeed K₄ embeds as a triangle with a single vertex inside connected to all three corners. Euler says F = 6 − 4 + 2 = 4 faces: three triangular inner faces plus the outer face.

Worked Example 2 — K₃,₃ is non-planar

K₃,₃ has n = 6, m = 9. It is bipartite, so the bipartite bound applies: m = 9 > 2n − 4 = 8. This alone proves non-planarity. The witness is trivial — K₃,₃ is itself the forbidden subgraph. The tool then highlights the 3 + 3 partition and 9 direct edges.

Worked Example 3 — The Petersen graph

The Petersen graph has n = 10, m = 15, so m ≤ 3n − 6 = 24 and the fast Euler checks pass. Yet it is famously non-planar. The checker locates a K₃,₃ subdivision: pick six vertices from the outer pentagon and inner pentagram so that every cross-pair can be routed through the remaining four vertices by vertex-disjoint paths. The tool draws the witness, making the 1930s geometry tangible.

Applications of Planarity

• VLSI and PCB routing. A single-layer circuit is feasible only if the connection graph is planar; non-planar nets force vias or extra layers.
• Graph drawing and visualisation. Planar graphs admit clear, crossing-free layouts — useful for metro maps, call graphs, and schematic diagrams.
• Algorithm design. Many NP-hard problems (maximum cut, vertex cover, graph isomorphism) become polynomial-time when restricted to planar graphs.
• Graph colouring. The Four Colour Theorem guarantees every planar graph is 4-colourable — a classical result whose statement depends on planarity.
• Combinatorial optimisation. Planar shortest path, max-flow and min-cut all admit specialised fast algorithms.
• Molecular chemistry. Benzene-ring aromatic-hydrocarbon graphs are planar; certain cage molecules are not.

Frequently Asked Questions

What does planar mean for a graph?

A graph is planar if you can draw it on the plane so that no two edges cross each other except at shared vertices. Equivalently, a graph is planar if and only if it can be drawn on the surface of a sphere without crossings. Trees, cycles, the cube graph, and the Platonic solids are all planar, while K₅ and K₃,₃ are the canonical non-planar examples.

What is Kuratowski's theorem?

Kuratowski's theorem states that a finite graph is planar if and only if it contains no subgraph that is a subdivision of K₅ or K₃,₃. A subdivision is obtained by replacing some edges with longer paths, each through brand-new degree-2 vertices. This gives a concrete combinatorial certificate of non-planarity.

What is the difference between K₅ and K₃,₃?

K₅ has 5 vertices, every pair of which is joined by an edge, for 10 edges total. K₃,₃ has 6 vertices partitioned into two groups of 3, with every vertex in one group connected to every vertex in the other, for 9 edges. Both are the smallest non-planar graphs of their kind, and together they form the forbidden minors for planarity.

How does Euler's inequality help?

Euler's formula V − E + F = 2 for planar connected graphs combined with the fact that every face of a simple planar graph has at least 3 edges yields m ≤ 3n − 6. Any simple graph violating this bound is immediately non-planar. For bipartite planar graphs every face has at least 4 edges, giving the tighter bound m ≤ 2n − 4. The checker applies both as fast rejection rules.

What is the size limit?

The checker handles up to 16 vertices and 60 edges. This covers typical teaching and competition-style graphs including the Petersen graph, the Möbius-Kantor graph, small hypercubes, and the complete graph K₇. Larger graphs require linear-time specialised planarity tests such as Hopcroft-Tarjan or left-right planarity.

How is the witness subdivision drawn?

When the graph is non-planar, the 5 branch vertices of the found K₅ — or the 6 branch vertices of K₃,₃ split into two triples A and B — are highlighted on an inner ring. The 10 (or 9) required internally vertex-disjoint paths are each drawn in a distinct colour so you can trace the K₅ or K₃,₃ topology visually. Vertices and edges that are not part of the subdivision are dimmed.

Further Reading

• Planar graph — Wikipedia
• Kuratowski's theorem — Wikipedia
• Euler characteristic — Wikipedia
• Petersen graph — Wikipedia
• Wagner's theorem (minor version) — Wikipedia