Graphiviz is useful graph- and network-layout software. You give it a description of a graph, as on the left:
and it produces a drawing of a graph as on the right. The first line says that node A is connected to B, which is connected to C. The second line says that B is also connected to D and F, but the edges should be dotted. The third line says that D is also connected to F, which is connected to E, which is connected to C.
Graphviz has several layout engines, which try to optimize layouts for
different kinds of properties. The example above uses the
I built a Graphiviz configuration file for the graph of U.S. state boundaries and put it in to see what would come out. The graph is naturally planar, and it will be interesting to see if the layout algorithms can detect that.
Here's what the U.S. actually looks like. (Source: Wikimedia Commons)
This is the output of Graphviz's default layout engine,
(Nodes here are labeled with their standard postal abbreviations. When you hover your pointer over a state name or other gegraphical designations in this article, the corresponding abbreviation will pop up. For example, New York should pop up a box with “NY”.)
The Mid-Atlantic, South Atlantic and Pacific coasts are clearly visible, Florida is dangling off the bottom, as it does. It's pretty amazing. The fact that the map is oriented correctly is a bonus. There are a few oddities: New England is where it should be, but Vermont should be switched with Connecticut and Rhode Island. South Carolina is sticking out into the Atlantic Ocean.
There is only one planarity failure, resulting from the inadvertent flipping of New England. The apparent crossing edge between Minnesota and Michigan is illusory; the edge could have been curved around Wisconsin with no trouble. (The real border between Minnesota and Michigan is a bit of an oddity, occurring in Lake Superior, and it really does leap over the head of Wisconsin that way.)
It has New England flipped over like
Now we move on to the odd ones. The
The geography is still correct here, more or less, with South at the top and East on the left. That puts Florida in the upper left and Washington in the lower right. But in between it's unexpectedly tangled. The central column states, ND-SD-NE-KS-OK-TX are all over the place.
So many questions here. What the heck is going on with Ohio and Michigan? And Illinois and