A quick peek at Wikipedia seems to indicate that they address only algorithms that avoid using graph drawing in the plane. But this doesn't sound like such a bad idea: Start with any embedding of the vertices in the plane, and slide them so that the sum of squared errors between the N choose 2 graph distances, and their corresponding planar distances, decreases to a local minimum (i.e., sliding down the gradient). Then check whether any two edges in the plane intersect. If they do, repeat this with a variety of starting embeddings in the hope of reaching the absolute minimum (up to scaling, say normalized by keeping [the sum of all n choose 2 planar distances] equal to a constant. --Dan P.S. This is a version of what's called multidimensional scaling. On 2013-02-17, at 12:25 PM, Gareth McCaughan wrote:
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. ... ...
But what about impossible maps? Or, to put it
in mathematical terms, a non-planar graph?
http://en.wikipedia.org/wiki/Planarity_testing briefly describes a few efficient ways of testing for planarity.