Planar graphs can be four-colored optimally in linear time
Four-Coloring Planar Graphs in Linear Time
Data Structures and AlgorithmsComputational GeometryDiscrete Mathematics
Summary
The famous four color theorem says any flat map can be colored with just four colors so that no touching regions share the same color. Finding such a coloring fast has been a challenge. The authors improved their previous method to color these maps in the fastest possible time, linear with the number of regions. They achieved this by cleverly reorganizing how changes are tracked and applied, using special data structures to speed up the process. This makes solving these coloring problems much more practical for large maps.
What this means in practice
- •For graph algorithm developers: Implement extremely fast planar graph coloring algorithms to speed up computations in geographic information systems and network analysis.
- •For computer graphics engineers: Use linear-time 4-coloring to efficiently assign colors in mesh processing tasks involving planar graphs.
Authors
Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Carsten Thomassen, Mikkel Thorup
Abstract
The famous Four Color Theorem (4CT) states that any planar graph can be colored with four colors, but how do we find a 4-coloring? In our previous paper [FOCS'26], we presented a simple combinatorial algorithm to 4-color planar graphs in $O(n\log n)$ time. We improve it here to $O(n)$ time, which is optimal. The algorithm from our previous paper is based on proving that every planar triangulation has a linear number of reducible configurations or obstructing cycles. The bottleneck for the algorithm is that we need $O(\log n)$ Kempe changes to extend a recursive 4-coloring to the reducible configurations. Each Kempe change can involve a constant fraction of the graph and takes linear time. Here we show that all $O(\log n)$ Kempe changes can be identified and implemented in $O(n)$ time. The idea is to spend $O(n)$ time to preprocess the graph so that we can identify and simulate each good Kempe change in $O(n/\log n)$ amortized time. Thus, we implement all $O(\log n)$ Kempe changes in $O(n)$ total time. Based on this, we implement the whole 4-coloring in linear time. We note that creating such a representation for fast identification and simulation of the right Kempe changes is a challenge of data structures, unlike the previous paper that builds on a new graph theoretic understanding of reducible configurations.