41.04Intermediate / Advanced5 topics16 min3 interactive animations

Planar graph topics

A planar graph can be drawn in the plane without crossing edges. Euler's formula links vertices, edges and faces, gives cheap edge-count bounds, and Kuratowski's theorem says that K5 and K3,3 are the only obstructions.

Learning goals

Define planarity and faces of a plane drawing
Use V − E + F = 1 + C and the bounds 3V − 6 and 2V − 4
State Kuratowski's theorem and spot K5 and K3,3
Explain the dual graph of a plane drawing

Prerequisites

Graph basics (Chapter 32)Graph colouring (Lesson 41.03)

Printed circuit boards, road maps and flow charts all want drawings without crossings. Planarity decides when that is possible, and the planar graphs turn out to be sparse, easy to colour and easy to compute with.

41.04.1

Planarity

A graph is **planar** if it can be drawn in the plane with vertices as points and edges as curves that meet only at shared endpoints. A **plane graph** is a particular such drawing. A graph may look tangled in one drawing and be planar in another: K4 drawn as a square with two crossing diagonals is planar because a triangle with a centre vertex draws it without crossings.

Deciding planarity is possible in linear time (Hopcroft-Tarjan, Boyer-Myrvold), but the algorithms are intricate. For graphs with at most 6 vertices there is a direct test from Kuratowski's theorem: the graph is non-planar exactly when it contains K3,3 as a subgraph, or K5 or K5 with one edge subdivided. The code below uses that, and the animation tests it on your input.

The planarity test also has a counting check that is a good sanity test for the implementation: the number of labelled planar graphs on 4, 5 and 6 vertices is 64, 1023 and 32071, and the only non-planar graph on 5 vertices is K5 itself.

Java

1// adj is the adjacency matrix of a simple graph with at most 6 vertices
2static boolean isPlanarSmall(boolean[][] adj) {
3    if (hasK33(adj) || hasK5Subdivision(adj)) return false;           // Kuratowski: these are the only obstructions
4    return true;
5}
6static boolean hasK33(boolean[][] adj) {                              // K3,3 as a subgraph: three vertices fully joined to the other three
7    int n = adj.length;
8    for (int a = 0; a < 1 << n; a++) {
9        if (Integer.bitCount(a) != 3) continue;
10        int b = ((1 << n) - 1) & ~a;
11        if (Integer.bitCount(b) != 3) continue;
12        boolean all = true;
13        for (int u = 0; u < n; u++) for (int v = 0; v < n; v++)
14            if ((a >> u & 1) == 1 && (b >> v & 1) == 1 && !adj[u][v]) all = false;
15        if (all) return true;
16    }
17    return false;
18}
19static boolean hasK5Subdivision(boolean[][] adj) {                    // with at most 6 vertices: K5, or K5 with one edge replaced by a path of length 2
20    int n = adj.length;
21    for (int s = 0; s < 1 << n; s++) {
22        if (Integer.bitCount(s) != 5) continue;
23        int missing = 0, mu = -1, mv = -1;
24        for (int u = 0; u < n; u++) for (int v = u + 1; v < n; v++)
25            if ((s >> u & 1) == 1 && (s >> v & 1) == 1 && !adj[u][v]) { missing++; mu = u; mv = v; }
26        if (missing == 0) return true;
27        if (missing > 1) continue;
28        for (int x = 0; x < n; x++) if ((s >> x & 1) == 0 && adj[mu][x] && adj[mv][x]) return true;   // a detour replaces the missing edge
29    }
30    return false;
31}
32// necessary conditions for a connected simple planar graph with v >= 3 vertices and e edges
33static boolean passesEulerBounds(int v, int e, boolean triangleFree) {
34    return e <= (triangleFree ? 2 * v - 4 : 3 * v - 6);
35}

Planarity: Euler's formula, edge bounds and Kuratowski's forbidden subgraphs

Interactive · edit the input

undirected graph · 4 vertices · 6 edges

Vertex of the forbidden subgraphEdge counted

Setup

V = 4 vertices, E = 6 edges, C = 1 connected component. A planar drawing has F faces (the outer one counts) with V − E + F = 1 + C, so a planar drawing of this graph would have F = 6 − 4 + 1 + 1 = 4 faces.

Step 1 / 4

Java

1// adj is the adjacency matrix of a simple graph with at most 6 vertices
2static boolean isPlanarSmall(boolean[][] adj) {
3    if (hasK33(adj) || hasK5Subdivision(adj)) return false;           // Kuratowski: these are the only obstructions
4    return true;
5}
6static boolean hasK33(boolean[][] adj) {                              // K3,3 as a subgraph: three vertices fully joined to the other three
7    int n = adj.length;
8    for (int a = 0; a < 1 << n; a++) {
9        if (Integer.bitCount(a) != 3) continue;
10        int b = ((1 << n) - 1) & ~a;
11        if (Integer.bitCount(b) != 3) continue;
12        boolean all = true;
13        for (int u = 0; u < n; u++) for (int v = 0; v < n; v++)
14            if ((a >> u & 1) == 1 && (b >> v & 1) == 1 && !adj[u][v]) all = false;
15        if (all) return true;
16    }
17    return false;
18}
19static boolean hasK5Subdivision(boolean[][] adj) {                    // with at most 6 vertices: K5, or K5 with one edge replaced by a path of length 2
20    int n = adj.length;
21    for (int s = 0; s < 1 << n; s++) {
22        if (Integer.bitCount(s) != 5) continue;
23        int missing = 0, mu = -1, mv = -1;
24        for (int u = 0; u < n; u++) for (int v = u + 1; v < n; v++)
25            if ((s >> u & 1) == 1 && (s >> v & 1) == 1 && !adj[u][v]) { missing++; mu = u; mv = v; }
26        if (missing == 0) return true;
27        if (missing > 1) continue;
28        for (int x = 0; x < n; x++) if ((s >> x & 1) == 0 && adj[mu][x] && adj[mv][x]) return true;   // a detour replaces the missing edge
29    }
30    return false;
31}
32// necessary conditions for a connected simple planar graph with v >= 3 vertices and e edges
33static boolean passesEulerBounds(int v, int e, boolean triangleFree) {
34    return e <= (triangleFree ? 2 * v - 4 : 3 * v - 6);
35}

Live state

4 vertices6 edges

No condition evaluated on this step

Execution trace (dry run table)Show 4 steps

Step	Line	State	What happens
1	L2	V=4 E=6 C=1	V = 4 vertices, E = 6 edges, C = 1 connected component. A planar drawing has F faces (the outer one counts) with V − E + F = 1 + C, so a planar drawing of this graph would have F = 6 − 4 + 1 + 1 = 4 faces.
2	L33	E=6 bound=6 triangleFree=no passes=yes	Every face is bounded by at least 3 edges and each edge borders two faces, so 3F ≤ 2E, which with Euler's formula gives E ≤ 3V − 6 = 6. This graph has 6 edges: the bound holds, which proves nothing yet.
3	L6	K33=none K5=none	No K3,3 subgraph and no K5 (or subdivided K5) on at most 6 vertices. By Kuratowski's theorem the graph is planar.
4	L4	return=planar faces=4	Planar. A crossing-free drawing has 4 faces (outer face included), by V − E + F = 1 + C.

41.04.2

Euler formula

**Euler's formula** says that a connected plane graph with V vertices, E edges and F faces (the unbounded outer face counts) satisfies V − E + F = 2. For a graph with C connected components the general form is V − E + F = 1 + C. So the number of faces of a plane drawing is fixed by the graph: F = E − V + 1 + C.

Every face is bounded by at least 3 edges, and every edge borders at most 2 faces, so 3F ≤ 2E. Substituting into Euler's formula gives E ≤ 3V − 6 for simple planar graphs with V ≥ 3. If the graph has no triangle, every face has at least 4 edges and the bound becomes E ≤ 2V − 4. These bounds show that planar graphs are **sparse**: they have O(V) edges.

Use them as quick rejections. K5 has 5 vertices and 10 edges, more than 3 · 5 − 6 = 9, so it is non-planar. K3,3 has 9 edges, below 3 · 6 − 6 = 12 but above the triangle-free bound 2 · 6 − 4 = 8, so it is non-planar as well. Passing the bounds proves nothing; the animation's “K5 with one edge subdivided” has 11 edges, within the bound 12, and is still non-planar.

Graph	V	E	Bound	Verdict
K4	4	6	3V − 6 = 6	6 ≤ 6, passes; planar, F = 4
K5	5	10	3V − 6 = 9	10 > 9, non-planar
K3,3	6	9	2V − 4 = 8 (no triangle)	9 > 8, non-planar
Two triangles	6	6	3V − 6 = 12	passes; planar, F = 6 − 6 + 1 + 2 = 3

Java

1// Euler's formula for a planar drawing: V - E + F = 1 + C, where F counts the outer face and C the connected components
2static int facesOfPlanarDrawing(int v, int e, int components) {
3    return e - v + 1 + components;
4}
5// faces are bounded by at least 3 edges (4 when there is no triangle) and every edge borders at most two faces
6static int maxEdgesOfPlanarGraph(int v, boolean triangleFree) {
7    return triangleFree ? 2 * v - 4 : 3 * v - 6;                      // valid for simple graphs with v >= 3
8}

Planarity: Euler's formula, edge bounds and Kuratowski's forbidden subgraphs

Interactive · edit the input

undirected graph · 4 vertices · 6 edges

Vertex of the forbidden subgraphEdge counted

Setup

Step 1 / 4

Java

1// adj is the adjacency matrix of a simple graph with at most 6 vertices
2static boolean isPlanarSmall(boolean[][] adj) {
3    if (hasK33(adj) || hasK5Subdivision(adj)) return false;           // Kuratowski: these are the only obstructions
4    return true;
5}
6static boolean hasK33(boolean[][] adj) {                              // K3,3 as a subgraph: three vertices fully joined to the other three
7    int n = adj.length;
8    for (int a = 0; a < 1 << n; a++) {
9        if (Integer.bitCount(a) != 3) continue;
10        int b = ((1 << n) - 1) & ~a;
11        if (Integer.bitCount(b) != 3) continue;
12        boolean all = true;
13        for (int u = 0; u < n; u++) for (int v = 0; v < n; v++)
14            if ((a >> u & 1) == 1 && (b >> v & 1) == 1 && !adj[u][v]) all = false;
15        if (all) return true;
16    }
17    return false;
18}
19static boolean hasK5Subdivision(boolean[][] adj) {                    // with at most 6 vertices: K5, or K5 with one edge replaced by a path of length 2
20    int n = adj.length;
21    for (int s = 0; s < 1 << n; s++) {
22        if (Integer.bitCount(s) != 5) continue;
23        int missing = 0, mu = -1, mv = -1;
24        for (int u = 0; u < n; u++) for (int v = u + 1; v < n; v++)
25            if ((s >> u & 1) == 1 && (s >> v & 1) == 1 && !adj[u][v]) { missing++; mu = u; mv = v; }
26        if (missing == 0) return true;
27        if (missing > 1) continue;
28        for (int x = 0; x < n; x++) if ((s >> x & 1) == 0 && adj[mu][x] && adj[mv][x]) return true;   // a detour replaces the missing edge
29    }
30    return false;
31}
32// necessary conditions for a connected simple planar graph with v >= 3 vertices and e edges
33static boolean passesEulerBounds(int v, int e, boolean triangleFree) {
34    return e <= (triangleFree ? 2 * v - 4 : 3 * v - 6);
35}

Live state

4 vertices6 edges

No condition evaluated on this step

Execution trace (dry run table)Show 4 steps

Step	Line	State	What happens
1	L2	V=4 E=6 C=1	V = 4 vertices, E = 6 edges, C = 1 connected component. A planar drawing has F faces (the outer one counts) with V − E + F = 1 + C, so a planar drawing of this graph would have F = 6 − 4 + 1 + 1 = 4 faces.
2	L33	E=6 bound=6 triangleFree=no passes=yes	Every face is bounded by at least 3 edges and each edge borders two faces, so 3F ≤ 2E, which with Euler's formula gives E ≤ 3V − 6 = 6. This graph has 6 edges: the bound holds, which proves nothing yet.
3	L6	K33=none K5=none	No K3,3 subgraph and no K5 (or subdivided K5) on at most 6 vertices. By Kuratowski's theorem the graph is planar.
4	L4	return=planar faces=4	Planar. A crossing-free drawing has 4 faces (outer face included), by V − E + F = 1 + C.

41.04.3

Faces

The **faces** of a plane graph are the regions the edges cut the plane into, including one unbounded **outer face**. The **boundary** of a face is the closed walk around it. A bridge (an edge whose removal disconnects the graph) has the same face on both sides, so it is counted twice in that face's boundary walk.

The **degree of a face** is the length of its boundary walk. Summing over all faces counts every edge exactly twice (once per side), so Σ deg(f) = 2E. This handshake lemma for faces is the engine behind the bounds of the previous section: if every face has degree at least g (the girth of the graph), then g · F ≤ 2E.

Which cycle becomes the outer face is a matter of choice: a plane graph can be redrawn so that any face is outer (by stereographic projection onto a sphere). Counting faces therefore does not depend on the drawing, only on the graph, which is exactly what the formula F = E − V + 1 + C expresses.

Plane graph	Faces	Face degrees
Triangle	2 (inside, outside)	3 and 3
K4 drawn without crossings	4	3, 3, 3, 3
A tree with 3 edges	1 (only the outer face)	6 (each edge counted twice)
Square with one diagonal	3	3, 3, 4

41.04.4

Kuratowski theorem overview

**Kuratowski's theorem** characterises planarity completely: a graph is planar if and only if it contains no **subdivision** of K5 or K3,3. A subdivision replaces edges by paths of length at least 1. Equivalently (Wagner's version), the graph has neither K5 nor K3,3 as a **minor**.

K5 is the complete graph on 5 vertices; K3,3 is the complete bipartite graph with three vertices on each side (the “three houses, three utilities” puzzle). Both are non-planar, and every non-planar graph contains one of them in disguise. That makes them the minimal obstructions: delete any edge of either and the result becomes planar.

A Kuratowski subgraph is also a short **certificate** of non-planarity, so planarity algorithms can return it when they fail. The animation shows such a certificate: it marks the six vertices of K3,3 or the vertices of the subdivided K5 that make a graph non-planar. The preset “K3,3 plus a chord” has triangles, so the cheap edge bound passes (10 edges ≤ 12) and only the Kuratowski search finds the obstruction.

Obstruction	Vertices	Edges	Why it is not planar
K5	5	10	10 > 3 · 5 − 6 = 9
K3,3	6	9	9 > 2 · 6 − 4 = 8 (no triangle)
Subdivision of K5 or K3,3	more	more	edges replaced by paths do not help the drawing

Java

1// adj is the adjacency matrix of a simple graph with at most 6 vertices
2static boolean isPlanarSmall(boolean[][] adj) {
3    if (hasK33(adj) || hasK5Subdivision(adj)) return false;           // Kuratowski: these are the only obstructions
4    return true;
5}
6static boolean hasK33(boolean[][] adj) {                              // K3,3 as a subgraph: three vertices fully joined to the other three
7    int n = adj.length;
8    for (int a = 0; a < 1 << n; a++) {
9        if (Integer.bitCount(a) != 3) continue;
10        int b = ((1 << n) - 1) & ~a;
11        if (Integer.bitCount(b) != 3) continue;
12        boolean all = true;
13        for (int u = 0; u < n; u++) for (int v = 0; v < n; v++)
14            if ((a >> u & 1) == 1 && (b >> v & 1) == 1 && !adj[u][v]) all = false;
15        if (all) return true;
16    }
17    return false;
18}
19static boolean hasK5Subdivision(boolean[][] adj) {                    // with at most 6 vertices: K5, or K5 with one edge replaced by a path of length 2
20    int n = adj.length;
21    for (int s = 0; s < 1 << n; s++) {
22        if (Integer.bitCount(s) != 5) continue;
23        int missing = 0, mu = -1, mv = -1;
24        for (int u = 0; u < n; u++) for (int v = u + 1; v < n; v++)
25            if ((s >> u & 1) == 1 && (s >> v & 1) == 1 && !adj[u][v]) { missing++; mu = u; mv = v; }
26        if (missing == 0) return true;
27        if (missing > 1) continue;
28        for (int x = 0; x < n; x++) if ((s >> x & 1) == 0 && adj[mu][x] && adj[mv][x]) return true;   // a detour replaces the missing edge
29    }
30    return false;
31}
32// necessary conditions for a connected simple planar graph with v >= 3 vertices and e edges
33static boolean passesEulerBounds(int v, int e, boolean triangleFree) {
34    return e <= (triangleFree ? 2 * v - 4 : 3 * v - 6);
35}

Planarity: Euler's formula, edge bounds and Kuratowski's forbidden subgraphs

Interactive · edit the input

undirected graph · 4 vertices · 6 edges

Vertex of the forbidden subgraphEdge counted

Setup

Step 1 / 4

Java

1// adj is the adjacency matrix of a simple graph with at most 6 vertices
2static boolean isPlanarSmall(boolean[][] adj) {
3    if (hasK33(adj) || hasK5Subdivision(adj)) return false;           // Kuratowski: these are the only obstructions
4    return true;
5}
6static boolean hasK33(boolean[][] adj) {                              // K3,3 as a subgraph: three vertices fully joined to the other three
7    int n = adj.length;
8    for (int a = 0; a < 1 << n; a++) {
9        if (Integer.bitCount(a) != 3) continue;
10        int b = ((1 << n) - 1) & ~a;
11        if (Integer.bitCount(b) != 3) continue;
12        boolean all = true;
13        for (int u = 0; u < n; u++) for (int v = 0; v < n; v++)
14            if ((a >> u & 1) == 1 && (b >> v & 1) == 1 && !adj[u][v]) all = false;
15        if (all) return true;
16    }
17    return false;
18}
19static boolean hasK5Subdivision(boolean[][] adj) {                    // with at most 6 vertices: K5, or K5 with one edge replaced by a path of length 2
20    int n = adj.length;
21    for (int s = 0; s < 1 << n; s++) {
22        if (Integer.bitCount(s) != 5) continue;
23        int missing = 0, mu = -1, mv = -1;
24        for (int u = 0; u < n; u++) for (int v = u + 1; v < n; v++)
25            if ((s >> u & 1) == 1 && (s >> v & 1) == 1 && !adj[u][v]) { missing++; mu = u; mv = v; }
26        if (missing == 0) return true;
27        if (missing > 1) continue;
28        for (int x = 0; x < n; x++) if ((s >> x & 1) == 0 && adj[mu][x] && adj[mv][x]) return true;   // a detour replaces the missing edge
29    }
30    return false;
31}
32// necessary conditions for a connected simple planar graph with v >= 3 vertices and e edges
33static boolean passesEulerBounds(int v, int e, boolean triangleFree) {
34    return e <= (triangleFree ? 2 * v - 4 : 3 * v - 6);
35}

Live state

4 vertices6 edges

No condition evaluated on this step

Execution trace (dry run table)Show 4 steps

Step	Line	State	What happens
1	L2	V=4 E=6 C=1	V = 4 vertices, E = 6 edges, C = 1 connected component. A planar drawing has F faces (the outer one counts) with V − E + F = 1 + C, so a planar drawing of this graph would have F = 6 − 4 + 1 + 1 = 4 faces.
2	L33	E=6 bound=6 triangleFree=no passes=yes	Every face is bounded by at least 3 edges and each edge borders two faces, so 3F ≤ 2E, which with Euler's formula gives E ≤ 3V − 6 = 6. This graph has 6 edges: the bound holds, which proves nothing yet.
3	L6	K33=none K5=none	No K3,3 subgraph and no K5 (or subdivided K5) on at most 6 vertices. By Kuratowski's theorem the graph is planar.
4	L4	return=planar faces=4	Planar. A crossing-free drawing has 4 faces (outer face included), by V − E + F = 1 + C.

41.04.5

Planar dual intuition

The **dual graph** G* of a plane graph G has one vertex for every face of G, and one edge for every edge of G: the dual edge crosses its primal edge and joins the two faces on either side of it. A bridge becomes a self-loop in the dual; parallel dual edges appear when two faces share several edges.

The dual swaps the roles of the counts: V* = F, E* = E and F* = V. The dual of the dual of a connected plane graph is the original graph. Euler's formula is symmetric under this exchange, which is a nice sanity check: V − E + F = F − E + V.

Duality turns problems into their counterparts. A cycle in G is a minimal cut in G*; a spanning tree of G corresponds to the complement of a spanning tree of G*; and colouring the faces of G (maps!) with four colours is the same as colouring the vertices of G* with four colours, which is how the Four Colour Theorem is stated for maps. Shortest paths in G* also give minimum cuts in G in planar flow problems.

Primal G	Dual G*
vertices V	faces: V* = F
edges E	edges E* = E (each edge crosses its dual)
faces F	vertices: F* = V
a cycle	a minimal edge cut
a spanning tree T	the dual edges NOT in T form a spanning tree of G*

Practice ladder

Now try it yourself

Easy

Island Perimeter

Medium

Number of Provinces

Advanced

Minimum Number of Days to Disconnect Island

Key takeaways

Planar graphs can be drawn without crossings; for connected plane graphs V − E + F = 2.
Planar simple graphs have E ≤ 3V − 6 (E ≤ 2V − 4 without triangles): they are sparse.
Kuratowski: non-planar exactly when K5 or K3,3 appears as a subdivision; duals swap vertices and faces.