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

  • $\begingroup$ I don't want to post a question about this myself, but I'm curious: are people still working on finding a digestible and conceptual (read: not computer aided) proof of the four color theorem? I kind of hope so... $\endgroup$ May 4 '11 at 0:49
  • $\begingroup$ @Paul: Some answers to your question can be found here: mathoverflow.net/questions/19240/… $\endgroup$
    – Tony Huynh
    May 4 '11 at 1:55
  • $\begingroup$ Hi Paul, I remember a comment made about this question by Noah Snyder. mathoverflow.net/questions/19240/…. "As far as I know there isn't anyone who is holed up in their attic thinking about only the 4-color theorem, instead there's a lot of people who every time they find a new tool think: hrm, I wonder if this tool would work on the 4-color theorem?" For example check the current reserch of Robin Thomas (people.math.gatech.edu/~thomas) $\endgroup$ May 4 '11 at 10:34
  • 1
    $\begingroup$ CS StackExchange has an informative thread entitled, "Conjectures implying the 4-color theorem," which may help providing different points of view: cstheory.stackexchange.com/questions/5659 $\endgroup$ May 4 '11 at 11:07

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.

  • $\begingroup$ I really like this one based on the circle packing theorem, thanks! $\endgroup$ May 6 '11 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.