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

- Published: 2026-11-19 13:31 UTC
- Section: Digital & Computing › Software & services
- Tags: four colour theorem, map colouring algorithm, linear time algorithm, planar graphs, reducible configurations, Mikkel Thorup, Carsten Thomassen, FOCS conference, graph colouring
- URL: https://realtech.media/news/rt-77bf7486642a7cf3c8515edd_thorup_thomassen_and/

**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](https://realtech.media/media/2026/11/dbe7fd78e46ccb42.jpg)
*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 [1]. Its running time grows linearly with map size, whereas earlier algorithms scaled quadratically [1]. The work is not a new proof of the four colour theorem but a search for an optimal way to carry it out [1].

## The theorem and the speed problem

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

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 [1].

## 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 [1]. Thomassen calls them "handles" that one can grab in order to begin filling in colours [1].

The team's main finding is that graphs contain many more of these handles than was previously thought [1]. Instead of colouring a map step by step, the algorithm can find many such points at once and colour regions in parallel [1]. 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 [1].

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 [1]. Thorup ironically calls the problem the "four-colour disease" [1]. 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 [1].

## Sources

1. [pravda.ru](https://www.pravda.ru/news/science/2445797-mathematicians-make)

---

Source: RealTech, realtech.media — https://realtech.media/news/rt-77bf7486642a7cf3c8515edd_thorup_thomassen_and/
