Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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... –  Paul Siegel May 4 '11 at 0:49
    
@Paul: Some answers to your question can be found here: mathoverflow.net/questions/19240/… –  Tony Huynh May 4 '11 at 1:55
    
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) –  Mario Stefanutti May 4 '11 at 10:34
1  
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 –  Joseph O'Rourke May 4 '11 at 11:07
    
Thanks for the comments and links! –  Paul Siegel May 6 '11 at 22:00

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
I really like this one based on the circle packing theorem, thanks! –  Mario Stefanutti May 6 '11 at 17:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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