Map graphs

[mtorpey]

Do we have anything much to do with map graphs? We can view a map (e.g. a map of the United States) as a graph where the different regions (e.g. US states) are the vertices, and an edge lies between two vertices whenever there is a border between two states.

Most of these are planar graphs, but we can have things like the Four Corners in the US, where four states meet at a point, and this makes map graphs a superset of the planar graphs. I think the mathematical definitions don't allow exclaves (disconnected segments of regions, like Russia's Kaliningrad oblast) which tend to confuse things, but I'm not sure of that.

I don't think we have anything to do with these, but it might be nice in future, perhaps as a student project. I'd like to see:

• An algorithm to determine IsMapGraph;
• Special ChromaticNumber/DigraphColoring methods (the maximum must be 4);
• A visual alternative to DotDigraph, to draw it as a map instead of a graph.

and I'm sure there's other great stuff to think about.