Planarity and Graph Coloring

Planarity and coloring are not just elegant math: PCB routing, compiler register allocation, exam scheduling, map coloring-all reduce to the same problem dressed differently.

• **Compilers:** LLVM and GCC use interference-graph coloring for register allocation, one of the most performance-critical compiler passes
• **Electronics:** PCB layout tools check planarity to determine how many copper layers a board requires
• **Scheduling:** university timetabling and job scheduling are graph coloring problems where colors represent time slots
• **Cartography:** the four-color theorem guarantees any geographic map can be printed with four ink colors

Предварительные знания

• Trees and Their Properties

Planar Graphs and Euler's Formula

A graph is **planar** if it can be drawn on a plane with no edges crossing. This is not merely a geometric curiosity: planarity determines whether circuits can be routed on a single board layer and affects the complexity of many algorithms.

**Euler's formula** for any connected planar graph: V − E + F = 2, where V = vertices, E = edges, F = faces (including the unbounded outer face). Consequence: for a simple planar graph with V ≥ 3, we have E ≤ 3V − 6.

Euler's formula gives a quick **necessary condition** for planarity: if E > 3V − 6, the graph is guaranteed non-planar. This is not sufficient, though: a graph can satisfy E ≤ 3V − 6 and still be non-planar (like K3,3 with E = 9 = 3×6−9). A complete characterization requires Kuratowski's theorem.

The formula V − E + F = 2 holds for any surface homeomorphic to a sphere. For a torus: V − E + F = 0. This is the **Euler characteristic** of the surface, a topological invariant.

Kuratowski's Theorem: K5 and K3,3

**Kuratowski's theorem (1930):** a graph is planar if and only if it contains no subgraph that is a subdivision of K5 (complete graph on 5 vertices) or K3,3 (complete bipartite graph). A **subdivision** is obtained by inserting degree-2 vertices into edges.

**K5:** 5 vertices, every pair connected (10 edges). **K3,3:** 6 vertices split into two triples, every vertex in the first triple connected to every vertex in the second (9 edges). K3,3 is the graph behind the classic 'three utilities problem': connecting three houses to three utilities (gas, water, electricity) without crossings is impossible.

Practical relevance: **PCB (printed circuit board) routing**. If the component connectivity graph is planar, all traces can be routed on a single copper layer without bridges. Most real boards are non-planar, requiring multiple layers precisely because they contain K5 or K3,3 subdivisions.

Planarity testing in O(V+E) is possible (Hopcroft-Tarjan, 1974), but the implementation is intricate. For practical use, rely on `networkx.is_planar()` or similar library routines rather than rolling a custom one.

Graph Coloring and Chromatic Number

A **proper coloring** assigns a color to every vertex so that no two adjacent vertices share a color. The **chromatic number χ(G)** is the minimum number of colors needed for a proper coloring. Computing χ(G) exactly is NP-hard in general.

**Four-color theorem (1976, Appel and Haken):** every planar graph has χ(G) ≤ 4. Equivalently, any map on the plane can be colored with four colors so that no two adjacent regions share a color. This was the first major theorem proved with computer assistance.

**Edge coloring:** assign colors to edges so that no two edges sharing a vertex get the same color. The **chromatic index** χ'(G) equals either Δ or Δ+1 (Vizing's theorem), where Δ is the maximum vertex degree. This gives a near-tight characterization, unlike vertex coloring.

Greedy Coloring and Register Allocation

**Greedy coloring:** visit vertices in some order, assigning each the smallest available color not used by its already-colored neighbors. The result is not guaranteed to be optimal, and the outcome depends heavily on the vertex ordering.

**Register allocation** is the canonical application of graph coloring in compilers. The interference graph has variables as vertices; an edge between two variables means they are simultaneously live and cannot share a register. The color is the register. If χ(G) exceeds the available registers, the compiler must spill some variables to memory.

**Exam scheduling** is another direct application. Courses with overlapping student enrollment cannot be scheduled at the same time. Build a conflict graph (vertices = courses, edges = shared students), then color it. The chromatic number gives the minimum number of time slots needed, and the coloring gives the actual schedule.

Greedy coloring in decreasing degree order (Welsh-Powell algorithm) or using the DSatur heuristic (choose the vertex with the most colored neighbors next) often achieves the chromatic number in practice, though optimality is not guaranteed. Exact χ(G) requires exponential-time algorithms or integer programming.

Key Ideas

• **Euler's formula:** V − E + F = 2 for connected planar graphs; consequence E ≤ 3V − 6
• **Kuratowski's theorem:** a graph is planar if and only if it has no K5 or K3,3 subdivision
• **Chromatic number χ(G):** minimum colors for a proper coloring; computing it exactly is NP-hard
• **Four-color theorem:** χ(G) ≤ 4 for every planar graph
• **Greedy coloring:** O(V+E), not optimal but widely used in compilers for register allocation

Related Topics

Planarity and coloring are advanced structural properties that build on core graph concepts.

• Trees and Their Properties — All trees are planar with chromatic number 2 (bipartite structure)
• Network Flows — Bipartite matching (χ = 2 graphs) can be solved optimally via max-flow
• Graph Theory Fundamentals — Planarity and coloring rely on the basic definitions of vertices, edges, and adjacency

Вопросы для размышления

• Why is computing the chromatic number NP-hard while planarity testing runs in O(V+E)?
• How does the compiler interference graph for register allocation relate to the exam scheduling problem?
• If a graph has a clique of size 4 (ω(G) = 4), what can you conclude about its chromatic number?

Связанные уроки

• comp-26-register-allocation