2008.6.2 Geo-graph experiments

I couldn't resist posting another one already. Here are a couple of graph-theoretical experiments I did a couple of days ago based on the states of the U.S. It's hard to believe that this first map wouldn't already have been done by someone before — I just haven't ever seen it. The states are represented by nodes — I took a screenshot of the U.S. in Google Maps and drew each node near the state's center of area, in most cases. When two states border each other, they are connected by a line. It's that simple.

a graph representation of the U.S. states

Although the states are unlabeled, once you figure out a few of the obvious ones, and then figure out some more based on those, it's pretty easy to deduce the rest. It's interesting to see how a few graceful arcs are built up across the graph. Another interesting piece was the North Dakota-Kansas-Nevada triangular lattice. I noticed that the same lattice structure extended east to Wisconsin and Illinois as well. So I decided to see if I could place all of the states into such a lattice and keep a connected graph. Now, the regular structure of this lattice would only be preserved over the whole U.S. for all of the lines of the graph if each interior state bordered exactly 6 other states. Because some states border fewer than 6 states and some border more, that isn't going to happen. In particular, Missouri and Tennessee each border 8 states and Kentucky borders 7. And since those three all border one another, that area caused the greatest degree of disruption to the lattice:

a graph representation of the U.S. states placed into a triangular lattice

The gray lines are all the ones from the first graph that fit into the lattice; the blue lines are the ones that didn't. Note that this is by no means the only way of configuring such a lattice, nor does this one necessarily minimize the number of blue lines.