Keith Lynch wrote:
I typed in a list of which US states border which other US states, so I can write programs to do various things with it. ... I only ran into trouble when attempting to verify that the list was correct. Well, not correct, necessarily, but consistent. Of course I made sure that if A borders B then B border A, and that no state borders itself. But what about impossible maps? Or, to put it in mathematical terms, a non-planar graph? This turns out to be surprisingly hard. I'm familiar with Kuratowski's theorem, but I estimate it would take at least a month of CPU time to test every possible set of 5 or 6 states. (No, applying it only to states that border each other is invalid.) And for larger maps, it would be completely infeasible. Of course I want any software I write to work with any map, not just with this map.
http://en.wikipedia.org/wiki/Planarity_testing briefly describes a few efficient ways of testing for planarity. -- g