Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A geographical map can always be modeled as a graph, such as the famous four-color problem. Does a graph always correspond to a map? In my point of view, planar graph can be done. So... 

Is there any method to prove that we cannot find a graph model for non-planar graph ? Maybe we can try to prove its contradiction that any map leads to a planar graph. But what's the rigorous proof?

share|improve this question
    
Only if the "countries" in the map are contiguous, which is not true in real life. See en.wikipedia.org/wiki/… –  Rahul Feb 12 '12 at 15:18
    
Alternatively, if you allow non-contiguous regions, then any graph can be drawn trivially by making a two-country island for each edge of the graph. –  Rahul Feb 12 '12 at 15:20

1 Answer 1

up vote 3 down vote accepted

The "intuition" here is that when a graph is planar, it can be drawn in the plane with regions that have different numbers of sides. This graph together with the regions the vertices and edges define is sometimes called a "map." However, isomorphic plane graphs can form regions with different numbers of sides and so one can argue that the maps are different - non-isomorphic. If a graph is planar and 3-connected then the map one gets is unique (a theorem of Whitney). Drawings in the plane of such graphs (which are known as the 3-polytopal graphs because they correspond to the vertex-edge graphs of convex 3-dimensional polyhedra) can look very different because one can chose different regions (with different numbers of sides when all the faces don't have the same number of sides) to be the unbounded face. When a graph is not planar one can not draw it in the plane without edges meeting at points other than vertices. However, one can draw such non-planar graphs on other surfaces than plane (surfaces of higher genus, like the torus) and one will get regions so that the "embedded graph" can be thought of as a map. Under the right conditions such maps of graphs behave very similarly to maps in the plane.

share|improve this answer

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.