Generating Graphs for the Earth-Moon Problem with Edge Flips: Revisiting Sulanke’s Algorithm

The Earth-Moon Problem is a problem in graph theory that extends the 4-colour theorem. The 4-colour theorem tells us that any planar map can be coloured with only 4 colours, such that bordering countries do not share a colour. The Earth-Moon problem is about the minimum number of colours required to colour any non-planar map that can be split into two planar graphs. Currently the problem is unsolved, but we do know that the maximum number of required colours is somewhere in between 9 and 12 colours. For our research we follow different leads, that might help narrow down the range of possible solutions of the Earth-Moon Problem. The main topic of our research is Sulanke's Algorithm: the best known algorithm for generating Earth-Moon graphs. This algorithm had been lost for over a decade, but has mostly been recovered in 2022. A lot of specifics about the algorithm are still lost though. We construct an adapted version of Sulanke's Algorithm that is both fast and efficient, by filling...Show moreThe Earth-Moon Problem is a problem in graph theory that extends the 4-colour theorem. The 4-colour theorem tells us that any planar map can be coloured with only 4 colours, such that bordering countries do not share a colour. The Earth-Moon problem is about the minimum number of colours required to colour any non-planar map that can be split into two planar graphs. Currently the problem is unsolved, but we do know that the maximum number of required colours is somewhere in between 9 and 12 colours. For our research we follow different leads, that might help narrow down the range of possible solutions of the Earth-Moon Problem. The main topic of our research is Sulanke's Algorithm: the best known algorithm for generating Earth-Moon graphs. This algorithm had been lost for over a decade, but has mostly been recovered in 2022. A lot of specifics about the algorithm are still lost though. We construct an adapted version of Sulanke's Algorithm that is both fast and efficient, by filling in the missing details. We also provide theorems to support the changes we made. In particular, we have a constructive proof that every edge-maximal planar graph can be obtained from any other edge-maximal planar graph with the same number of vertices, by applying so called edge flips. This proof is a new result, which shows that Sulanke's Algorithm can generate all graphs we are interested in We also cover new discoveries made by Tilley on the 4-colour theorem and we investigate whether these discoveries can be extended to be used for solving the Earth-Moon problem. We also discuss some of our own ideas for solving the Earth-Moon problem. We did not have any breakthroughs, but our research does provide more clarity on potentially useful strategies potentially for solving the Earth-Moon problem.Show less

Leiden University Student Repository

Documents

In Collections

Generating Graphs for the Earth-Moon Problem with Edge Flips: Revisiting Sulanke’s Algorithm