Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 36 ยท Planarity and Flows

Kuratowski's Theorem and Planarity Checking

Learn Kuratowski's and Wagner's theorems, graph minors and subdivisions, and test planarity in Python with rotation systems and a K5/K3,3 minor search.

Euler's edge bound can prove that a graph is not planar, but it can never prove that a graph is planar. We need a complete characterization: a test that works for every graph. In 1930 Kazimierz Kuratowski found one in terms of two small forbidden graphs, and later Klaus Wagner reformulated it using graph minors. In this lesson you will learn both statements and then test planarity yourself in two completely different ways.

Subdivisions and minors

A subdivision of a graph replaces some edges by paths: put new degree-2 vertices in the middle of an edge. Subdividing an edge does not change planarity, because a drawing can follow the longer path just as well.

A minor of G is any graph obtained by deleting vertices, deleting edges and contracting edges (merging the two endpoints into one vertex). Every subdivision of H that sits inside G gives H as a minor, but minors are more general: contracting a connected blob of vertices into one vertex is allowed.

Kuratowski's theorem. A graph is planar if and only if it contains no subdivision of K5 or K3,3.

Wagner's theorem. A graph is planar if and only if it has no K5 or K3,3 minor.

K5 ("five houses, all pairs connected") and K3,3 (the "three utilities problem": connect three houses to gas, water and electricity without crossings) are the two atoms of non-planarity. Any non-planar graph hides one of them, possibly stretched into paths. The Petersen graph, for instance, contains a subdivision of K3,3 even though it has no K5 subdivision.

flowchart LR
    A["Is G planar?"] --> B{"Contains a K5 or K3,3 subdivision?"}
    B -->|"yes"| C["Not planar"]
    B -->|"no"| D["Planar, a drawing exists"]

Kuratowski's theorem turns "can be drawn" into "avoids two forbidden structures".

Test 1: rotation systems

Recall from Euler's formula that tracing faces needs only the cyclic order of neighbors around each vertex, called a rotation system. Every rotation system defines an embedding on some surface, and the number of faces F it produces satisfies V โˆ’ E + F = 2 โˆ’ 2g where g is the genus of that surface. The graph is planar exactly when some rotation system reaches g = 0, that is, F = 2 โˆ’ V + E.

For small graphs we can simply try all rotation systems (each vertex of degree d has (d โˆ’ 1)! cyclic orders). This is exponential, so it is only a teaching tool, but it is a complete and correct planarity test for connected graphs, and the best face count even yields the graph's genus.

Python Planarity and genus by trying all rotation systems

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

K4 and the cube are planar (genus 0). K3,3, K5 and the Petersen graph all need a torus (genus 1): you can draw them on a doughnut without crossings, but not on a plane.

Test 2: searching for a forbidden minor

The second test follows Wagner's theorem literally. In a connected graph, H is a minor exactly when you can contract edges until only |V(H)| vertices remain and the result contains H; any leftover vertices can be absorbed into a neighboring branch set. So we explore all ways of contracting edges, remembering graphs we have seen, and look for K5 (complete on 5 vertices) or K3,3 (a 3+3 split with all nine crossing edges).

Python Find a K5 or K3,3 minor by contracting edges

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The result agrees with the rotation-system test: the Petersen graph and the subdivided K3,3 are non-planar; the cube, the wheel and K4 are planar. The Petersen graph shows why minors and subdivisions differ. Its maximum degree is 3, so it has no K5 subdivision (every branch vertex of K5 needs degree 4). Yet contracting its five "spoke" edges produces K5 itself, so it has a K5 minor, and it also contains a genuine K3,3 subdivision.

Real planarity algorithms

Neither of our tests scales. Real libraries use linear-time algorithms:

  • Hopcroft-Tarjan (1974): the first linear-time test, based on depth-first search and splitting the graph at cycles.
  • Left-right planarity test (de Fraysseix and Rosenstiehl): a DFS that assigns each back edge to the "left" or "right" side. The graph is planar iff such an assignment is consistent. It is used by NetworkX's check_planarity.
  • Boyer-Myrvold: incremental embedding; returns either an embedding or a Kuratowski subgraph as a certificate.

All of them run in O(V) time, since a planar graph has at most 3V โˆ’ 6 edges. Planarity is also the gateway to a world of theory: graph minor theory (Robertson and Seymour) proves that every minor-closed property is characterized by a finite list of forbidden minors, with planarity as the best-known example.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What are the two forbidden structures in Kuratowski's theorem?

    A graph is planar exactly when it contains no subdivision of the complete graph K5 or the complete bipartite graph K3,3.
  2. 2. How does Wagner's theorem differ from Kuratowski's?

    Wagner's version says a graph is planar iff it has neither K5 nor K3,3 as a minor, so contraction is allowed as well as subdividing.
  3. 3. What does a rotation system record?

    The circular order of incident edges at each vertex is enough to trace faces and compute the genus of the embedding.
  4. 4. Why is the Petersen graph not planar although it satisfies E โ‰ค 3V โˆ’ 6?

    Passing the edge-count test is not enough. Kuratowski's theorem is the complete criterion, and the Petersen graph contains a subdivision of K3,3.

Summary

  • Subdividing an edge keeps planarity; minors also allow vertex/edge deletion and edge contraction.
  • Kuratowski: planar iff no subdivision of K5 or K3,3; Wagner: planar iff no K5 or K3,3 minor.
  • A graph is planar iff some rotation system yields V โˆ’ E + F = 2; otherwise the best rotation system gives its genus.
  • Linear-time planarity tests (Hopcroft-Tarjan, left-right, Boyer-Myrvold) exist and are used in practice.

Next: Maximum Flow and the Ford-Fulkerson Method