[Math] Representations of regular maps (four color theorem)

gn.general-topologygraph theorygraph-colorings

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
  • As circle packing

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)
  • …

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

And here are other representations after the comments received:

UPDATE: 19/May/2011 – Added other representations of graphs

Best Answer

In my opinion these different representations don't help in understanding the four color theorem, but another example is circle packings (http://en.wikipedia.org/wiki/File:Circle_packing_theorem_K5_minus_edge_example.svg). There are also various reformulations of the four color theorem that are less transparent than representing graphs in other ways; see for instance http://www.math.uic.edu/~kauffman/MapReform.pdf.

Related Question