Four color theorem: representations of maps

For the scope of the four color problem and without lack of generality, maps can be represented in different ways. This is generally done to have a different perspective on the problem.

For example, the graph-theoretic representation of maps has become so common and important that generally the four color problem is stated and analyzed directly in terms of graph theory: http://en.wikipedia.org/wiki/Four_color_theorem.

I am trying to collect other representations that may in some way help to get a different point of view on the problem. If you know one of these representations that is not listed and wish to share, report it here. If you also have a web reference that explains or shows the representation, it would be great.

The representations have to be general and applicable to all maps with the simplification that only regular maps (no exclaves or enclaves, 3 edges meeting at each vertex, etc.) can be considered.

These are some classic representations:

• Natural: As a 3-regular planar graph (boundaries = edges)
• Canonical: As the dual graph of the “natural” representation (region = vertex, neighbors = edges)
• As a straight line drawing graph (Fáry’s theorem)
• As a graph with vertices arranged on a grid
• As a rectilinear cartogram

Plus, I found these:

• As a circular map
• As a rectangular map
• As clefs (derived from rectangular maps)
• As pipes map (derived from the clefs representation)
• …

New representations (answers from mathoverflow):

• http://en.wikipedia.org/wiki/Circle_packing_theorem (Koebe–Andreev–Thurston theorem)
• As hypergraphs induced by discs (see: “ON THE CHROMATIC NUMBER OF GEOMETRIC HYPERGRAPHS” by SHAKHAR SMORODINSKY)

Here is an example of some of these representations for the original map shown:

See next post for other representations.