Earth–Moon problem
In mathematical terms, it seeks the chromatic number of biplanar graphs.
One real-world application of the Earth–Moon problem involves testing printed circuit boards.
In the map coloring problem, finitely many simply connected regions in the Euclidean plane or a topologically equivalent space, such as countries on the surface of the Earth, are to be colored so that, when two regions share a boundary of nonzero length, they have different colors.
It can be transformed into a graph coloring problem by making a vertex for each region and an edge for each two neighboring regions, producing a planar graph whose vertices are to be colored.
[2] In 1959, Gerhard Ringel published a book on colorings of surfaces, surveying the results at the time on the four color problem and the Heawood conjecture on coloring maps on non-planar surfaces such as the torus and Klein bottle.
Ringel himself later proved the Heawood conjecture in a 1968 paper with J. W. T. Youngs;[2][3] the four-color theorem evaded proof until 1976.
[2][4] Another topic of Ringel's book was a result of Percy John Heawood from 1890, on the "empire problem": coloring maps in which each empire has some number
of distinct regions on the Earth (a home country and
[1][2] In a formulation of Martin Gardner, the colonies are instead on Mars.
[6] In Ringel's Earth–Moon problem, each country on the Earth has a corresponding colony on the surface of the Moon, that must be given the same color.
[2] Ringel proved that the number of colors needed was at least 8 and at most 12, conjecturing that 8 was the correct answer.
[6] Again, one can phrase the same question equivalently as one in graph theory, with a single vertex for each pair of a country and its colony, and an edge for each adjacency between countries or colonies.
The graphs that result in this version of the problem are biplanar graphs, or equivalently the graphs of thickness two: their edges can be partitioned into two subsets (the edges coming from Earth adjacencies and those coming from Moon adjacencies) such that the corresponding two subgraphs are both planar.
In mathematical terms, Ringel's problem asks for the maximum chromatic number of biplanar graphs.
edges (double the number that a planar graph can have), from which it follows from the degree sum formula that it has at least one vertex with at most 11 neighbors.
[2] This construction, by Thom Sulanke in 1974, disproved the conjecture of Ringel that 8 colors would always suffice.
Additionally, they meet the bounds on the number of edges a biplanar graph can have.
However, a representation of them as biplanar graphs (or Earth–Moon maps) remains elusive.
The electrical conductors within these boards include crossings, but (for double-sided printed circuit boards) their adjacencies can be assumed to form a biplanar graph.
With some care, this idea can be used to reduce the number of tests needed per circuit to only four.
[12][13] Maps with one planet and multiple regions per country give Heawood's empire problem.
