digraphs
Map graphs
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/DigraphColoringmethods (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.
