Mathematics.

graph structures

Planar Graphs

Graph Theory30 minDifficulty4 out of 10

You should know: graph basics

Overview

A planar graph is a graph that can be drawn on a plane with no two edges crossing. Euler's formula relates the number of vertices, edges, and faces of any connected planar drawing: V - E + F = 2. This formula yields a hard edge bound for simple planar graphs: E ≤ 3V - 6 (for V ≥ 3), which is used to prove that graphs like K5 (the complete graph on 5 vertices) and K3,3 (the complete bipartite graph on two sets of 3) are NOT planar. Kuratowski's theorem sharpens this into a full characterization: a graph is planar if and only if it contains no subdivision of K5 or K3,3 as a subgraph. Planarity matters directly for circuit board layout, where crossing wires require extra layers.

Intuition

Think of a road map or circuit board: a planar graph is one you can draw so that roads (or wires) never have to cross each other except at an actual intersection (vertex). This is why single-layer printed circuit boards can only implement planar circuits — any wiring diagram that needs edge crossings must either add a physical jump (a second layer) or accept the crossing, exactly mirroring the mathematical fact that not every graph is planar.

Formal Definition

Definition

For a connected planar graph drawn with V vertices, E edges, and F faces (including the unbounded outer face):

V−E+F=2V - E + F = 2
Euler's formula for planar graphs
E≤3V−6(V≥3)E \le 3V - 6 \quad (V \ge 3)
Edge bound for simple planar graphs
Kuratowski: G is planar  ⟺  G has no subdivision of K5 or K3,3\text{Kuratowski: } G \text{ is planar} \iff G \text{ has no subdivision of } K_5 \text{ or } K_{3,3}
Kuratowski's theorem

Worked Examples

  1. Apply Euler's formula V - E + F = 2 and solve for F.

    4−6+F=24 - 6 + F = 2

  2. Solve: F = 2 - 4 + 6 = 4.

    F=4F = 4

Answer: 4 faces (this matches the tetrahedron graph K4, drawn planar with 3 triangular faces plus the outer face).

Practice Problems

Difficulty 3/10

A connected planar drawing has 6 vertices and 5 faces. How many edges does it have, by Euler's formula?

Difficulty 5/10

A single-layer circuit board needs to connect 6 components such that every wire is planar (no crossings). Why does the planar edge bound E ≤ 3V - 6 tell a circuit designer something practical?

Difficulty 4/10

K3,3 (complete bipartite graph, two sets of 3 vertices, all 9 cross edges present) is famously non-planar. Verify it doesn't violate the E ≤ 3V-6 bound directly, and explain why it's still non-planar.

Quiz

Euler's formula for a connected planar graph states:
Kuratowski's theorem characterizes planar graphs as those containing no subdivision of:
For a simple planar graph with V ≥ 3 vertices, the number of edges satisfies:

Summary

  • A planar graph can be drawn in the plane with no edge crossings; Euler's formula gives V - E + F = 2 for any such connected drawing.
  • The bound E ≤ 3V - 6 (or E ≤ 2V - 4 if triangle-free) is used to prove graphs like K5 and K3,3 are non-planar.
  • Kuratowski's theorem fully characterizes planarity: a graph is planar iff it contains no K5 or K3,3 subdivision.

References

  1. WebsiteWikipedia — Planar graph