Digital › Software2 min read

Thorup, Thomassen and colleagues present a linear-time four-colouring algorithm for planar maps at FOCS

A new algorithm for four-colouring planar maps runs in linear rather than quadratic time: a map 10 times larger takes 10 times longer to process, not 100 times.

Thorup, Thomassen and colleagues present a linear-time four-colouring algorithm for planar maps at FOCS
Photo: pravda.ru

An international group of researchers, including Mikkel Thorup of the University of Copenhagen and Carsten Thomassen of the Technical University of Denmark, presented a new algorithm for colouring planar maps with four colours at the Foundations of Computer Science (FOCS) conference, according to pravda.ru pravda.rupravda.rupravda.ruOpen source ↗. Its running time grows linearly with map size, whereas earlier algorithms scaled quadratically. The work is not a new proof of the four colour theorem but a search for an optimal way to carry it out.

The theorem and the speed problem

The statement that four colours suffice for any planar map was formulated by Francis Guthrie in 1852. The first proof, found in 1879, turned out to be wrong, and a final answer was obtained only in 1976 with a computer program. The theorem is considered solved, but there was a gap between knowing that a colouring exists and having a fast method to produce it.

With the earlier algorithms, computation time grew quadratically. If the number of regions increased 10 times, the computation took 100 times longer, which made large datasets hard to handle.

Reducible configurations as starting points

The researchers worked with planar graphs, which are sets of points joined by lines. Such graphs contain so-called reducible configurations, specific combinations of connections that can serve as starting points for colouring pravda.rupravda.rupravda.ruOpen source ↗. Thomassen calls them "handles" that one can grab in order to begin filling in colours.

The team's main finding is that graphs contain many more of these handles than was previously thought. Instead of colouring a map step by step, the algorithm can find many such points at once and colour regions in parallel. This moves the computational complexity from quadratic to linear: a map 10 times larger now slows the calculation by a factor of 10, not 100.

The researchers note that the approach also works for surfaces with holes, such as objects shaped like a torus or a piece of cheese with holes. Thorup ironically calls the problem the "four-colour disease". According to the report, the solution offers new tools for other hard mathematical puzzles that require fast search through options and the identification of optimal structures.

Sources · 1

Found a mistake?
  1. ↩

Read also

Up next

The next story opens automatically

More
Follow us

Type at least two letters — results appear instantly

↑↓to choose↵to openescto close