Representations of regular maps (four color theorem) - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T12:57:55Z http://mathoverflow.net/feeds/question/63861 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/63861/representations-of-regular-maps-four-color-theorem Representations of regular maps (four color theorem) Mario Stefanutti 2011-05-03T23:20:50Z 2011-06-08T06:35:12Z <p>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.</p> <p>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: <a href="http://en.wikipedia.org/wiki/Four_color_theorem" rel="nofollow">http://en.wikipedia.org/wiki/Four_color_theorem</a>.</p> <p>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.</p> <p>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.</p> <p>These are some classic representations:</p> <ul> <li>Natural: As a 3-regular planar graph (boundaries = edges)</li> <li>Canonical: As the dual graph of the "natural" representation (region = vertex, neighbors = edges)</li> <li>As a straight line drawing graph (Fáry's theorem)</li> <li>As a graph with vertices arranged on a grid</li> <li>As a rectilinear cartogram</li> <li>As circle packing</li> </ul> <p>Plus, I found these:</p> <ul> <li>As a circular map</li> <li>As a rectangular map</li> <li>As clefs (derived from rectangular maps)</li> <li>As pipes map (derived from the clefs representation)</li> <li>...</li> </ul> <p>Here is an example of some of these representations for the original map shown:</p> <p><img src="http://4coloring.files.wordpress.com/2011/05/representations-of-maps-v2.png"/></p> <p>And here are other representations after the comments received:</p> <p><img src="http://4coloring.files.wordpress.com/2011/05/other-representations-of-maps.png"/></p> <p>UPDATE: 19/May/2011 - Added other representations of graphs</p> http://mathoverflow.net/questions/63861/representations-of-regular-maps-four-color-theorem/63864#63864 Answer by Richard Stanley for Representations of regular maps (four color theorem) Richard Stanley 2011-05-04T00:29:18Z 2011-05-04T00:29:18Z <p>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 <a href="http://www.math.uic.edu/~kauffman/MapReform.pdf" rel="nofollow">http://www.math.uic.edu/~kauffman/MapReform.pdf</a>.</p>