How Graphviz thinks the USA is laid out | Hacker News Reader

How Graphviz thinks the USA is laid out

shitpost.plover.com

234 pointssigna1180 comments

Open articleView on HN

I tried the same thing in 2004 with the London Underground map connections. It was not entirely a disaster.

https://f000.backblazeb2.com/file/rjp-hosted-files/bigneatot...

(Also the linked graphviz file has FL only linked to GA - surely it should have AL as well since AL is linked to FL?)

Maybe, qvge (editor for graphs) may help you.

https://github.com/ArsMasiuk/qvge

This was just to see if an automatic layout algorithm could make sense of connections between stations. ("Kinda. If you squint.")

I don’t have the image at hand anymore, but I did Brazilian states (with Graphviz defaults) many years ago and boy, it was excellent.

It amuses me how the Northern line is generally the right shape, but is upside down.

Florida is already linked to Alabama at the top:

  > AL -- FL, GA, MS, TN

Oh, yeah, but I figured it'd include both links, not just the first one alphabetically. But I guess it doesn't make much odds either way.

A physical adjacency graph of fairly regular shapes will end up resembling the original arrangement, when laid out to minimize edge lengths.

See also: US map made entirely out of rectangles

https://www.reddit.com/r/MapPorn/comments/bg8e7v/united_stat...

OR dominates the west coast!

I would like to see this done more granularly (counties?) and again using population flows to weight edges (and thus introducing non-local edges). I’m somewhat surprised I’ve never seen this before and think it’d be very illustrative.

These are commonly drawn in circular layout, like this: https://sites.google.com/a/parishepiscopal.org/mr-rick-dunn/....

It'd be fun to see this for the whole world. It would also make it easy to compute the answers to common quiz questions involving doubly landlocked countries, countries with most borders, etc.

here's the whole world done this way using Wikidata https://twitter.com/derenrich/status/1228508337559392261/pho... but the labels are removed and it includes maritime borders to make it a (very hard) guessing game

Curiously that doesn't seem to be accessible without logging in to Twitter, and I'm not inclined to do so at the moment; do you have another link to the game?

odd. the link works for me in a logged out/incognito window.

here's an imgur link: https://imgur.com/a/MppJE4c

Yeah, I'm not sure what to make of it. Can't remember the last time Twitter told me I couldn't retrieve a link...

And this time I checked, it's accessible. Must have been a transitory glitch.

Thanks.

I’m seeing that too sometimes, a refresh usually fixes it.

I think Twitter might be throttling anonymous/not logged in users. On desktop, where I'm logged in I've never had an issue with retrieving content, on mobile, where I'm not, no matter the browser, it's hit or miss (I'd estimate around 30% of the time I need to refresh)

Did you open it in a tab that was not immediately made active?

There seems to be some sort of issue with Twitter whereby the javascript to fetch/render the tweet doesn't fire if you open it in a background tab and then visit the tab.

Refreshing the page causes the javascript to correctly fire and the tweet is displayed. This is due to Twitter no longer pre-rendering the page server side, its all done client side.

Also makes it impossible to use Twitter from a browser with javascript disabled.

This is mostly an artifact of how eastern states states are smaller because most states on accession to the union were within an order of magnitude vs peers population wise and the east was much more densely populated.

I do wonder though if the west coast wouldn't be better managed if the states were split up a bit more population wise like in the east.

The decision to say Michigan borders Minnesota and Illinois is weird to me. They have borders that are in the water and none on land.

So? The political boundaries between the states lie inside Lake Superior and Lake Michigan, respectively.

PA is similarly disconnected from NJ via the Delaware river, would you also say they don't border each other?

https://en.wikipedia.org/wiki/Delaware_River#/media/File:Del...

Lake Superior is the largest freshwater body of water in the world. Claiming there isn’t a material difference between that and the Delaware River is weird.

When we are looking at a map of the US, they don’t draw the Delaware River. They do draw the Great Lakes.

> freshwater body

This implies volume. Baikal doubles LS in this respect.

I think it implies surface area.

Lake Michigan-Huron is hydrologically just one lake and outsizes Lake Superior.

So in your mind Alaska borders Texas?

Your comment is a good example of a strawman.

No, it’s a serious question as topologically they do border each other. So, are they arguing being able to sail from A to B is enough or must they be sailing across freshwater etc. Borders do get drawn across bodies of water all the time, but deciding if France and the UK border each other but Spain and Italy don’t is arbitrary.

It's not arbitrary. You can get from France to UK without entering international waters, and without crossing waters controlled by another entity.

I don't think you can do that with Spain and Italy? To get from one to the other you'd have to go through French or Algerian waters I think.

And I might be agreeing with you; not sure here. Conversation went from rivers to lakes to "a coffee cup is the same as a donut" pretty quickly :)

Spain is the closest country to some parts of Italy. So, they limit each others economic exclusion zones. That said it’s close to 400 miles between them across open ocean. Further economic exclusion zones are a fairly recent and thus an arbitrary thing.

Minorca and Sardinia give you a path that avoids other countries’ waters, it seems (https://www.researchgate.net/figure/The-Hypothetical-200nm-l...)

Land borders are also arbitrary.

Topologically, Alaska borders Texas.

Politically, since you can't walk from one to the other without crossing intervening political entities or relying on bulk transportation carriers, no.

Then again, same with Minnesota and Michigan.

Get in a row boat in Michigan. Row really hard. You can get to Minnesota without crossing any other border. And you'll come out the other side with ripped arms!

People can make the Atlantic crossing in a rowboat as well. https://www.cnn.com/2020/04/29/uk/rowing-solo-trans-atlantic...

I suspect with the right boat someone could row from Alaska to Texas. Though it would probably take a full year.

Yeah, but those would leave US territorial waters....

That may be the real key. Michigan to Minnesota stays within US territory. New York to Rhode Island and Providence Plantation stays within US territory. Texas to Alaska does not, no matter which mode of travel you chose. Texas to New York might. Shall we go there?

It depends how oceans count as far as state barriers go.

I have to imagine that going from Texas to New York along the coast would hit a state border somewhere around Louisiana.

Adding bodies of water (great lakes, gulf, 2 oceans) may help fix the Rhode island issue and this one. Or perhaps make it worse (my expectation is they'd act as anchors of a sort)

We are talking about a political map. So the essential question is: Are the Great Lakes managed by the federal government or by the states?

The answer to the question is yes.

>They have borders that are in the water and none on land.

So? They still have borders. Borders are a geopolitical construct (that is, decided by treates and politics), not a geographical.

They are merely informed/influenced by geography.

> Ah, then the post should have gone farther: every coastal state, including Alaska and Hawaii, should have been bordered by each other.

That's not how geopolitical borders work. A country's segments (e.g. states) could have borders between them, but that doesn't mean that each has border with each other.

They just all belong to the same entity (e.g. here, the US).

(And state borders != country borders).

What does that mean? What is the difference between "borders" and "border"?

Sufficiently far out from land (IIRC 10 miles) the ocean becomes "international waters", and no country legally controls it. There's a border between the territorial waters of a given country and these international waters along the coast.

There's also noun/verb confusion. A state has borders (noun). A state can border another (verb). State A has a border, state B has a border, and A borders B.

California has a border with International Waters. Hawaii is directly surrounded by International Waters. California does not border Hawaii, though both have borders and border International Waters.

No difference, that grammatical change from plurar to singural wasn't part of my point. You can also read it as:

"A country's segments (e.g. states) could have borders between them, but that doesn't mean that each has borders with each other."

Another commenter explained what I meant well, but here's my explanation:

The US might have a border with Canada, but doesn't mean that Colorado also has a border with Canada.

Similarly, Alaska and Hawaii might be part of the US, and thus their borders are the US borders too, but that doesn't mean e.g. Hawaii borders Nebraska.

Now borders might be on land or on water, but they're still borders. As long as another entity is not in between (e.g. Canada, as is the case between e.g. US and Alaska, or the Ocean between the US and Hawaii).

Many states have borders in the middle of a river. Just pretend the lakes are wide rivers, topologically.

What about California and Hawaii or Alaska then? Where do you draw the line?

International borders? There is not-US between each of Hawaii and Alaska and any other part of the country.

There is no not-US between Michigan and Minnesota.

> There is not-US between each of Hawaii and Alaska and any other part of the country.

What's the not-US between Hawaii and California?

Update: oops, I get it. The ocean itself. Never mind, move along, nothing to see here.

State territories, which include the waters of the Great Lakes but not the entirety of the Pacific Ocean

I would draw the line when I could stand on one shore and not visually see the other side.

I assume RI is "bordering" NY because of the ferry to Block Island, but this feels somewhat wrong to me...

Came here to comment on this too. I guess the author included the maritime borders?

https://en.m.wikipedia.org/wiki/Geography_of_New_York_(state...

State territory includes certain waterways. If two states' territories meet in the water, it counts.

I wonder how a SOM [1] would lay it out.

[1] https://en.wikipedia.org/wiki/Self-organizing_map

Different kind of map.

The idea of optimizing a graph layout based on the subject matter that its modeling is a really interesting idea. I'm in the camp of always interested in more visual programming techniques / aids, so it would be really great for us to be able to visualize something as complex as a large program this way.

I've used dot+graphviz to visualize algorithms and data structures before. The syntax makes it really easy to get started with, just print out "x -> y;" in your inner loop or whatever.

I'll wager the New England problem could be resolved by reordering the input data. GraphViz outputs are not independent of the ordering of inputs.

What is the New England problem? Hard to google for this.

It's from the article. Some of the New England states get flipped around relative to their actual geographic positions:

> New England is where it should be, but Vermont should be switched with Connecticut and Rhode Island.

It's funny that he would notice that but not notice that RI and CT are reversed in his graph. E.g.,

  NY -- PA, RI, VT

New York borders Connecticut, but not Rhode Island.

There is a water border between long island and Rhode Island.

New York borders Rhode Island in the water.

Google maps shows a border.

https://www.google.com/maps/place/Long+Island+Sound/@41.3418...

Would it help to provide more information by adding edge weight as the length of the shared border between the two states?

Weighted by distance between capitals perhaps.

Hmm, good idea. Or weighted by distance between midpoint of state?

The idea being that, to my knowledge, the state capitals are not in the middle always, thus leading to some form of distortion.

Capitals can be very much eccentric in a state (the distance from Cheyenne, Wyoming to Helena, Montana is (eyeballing) about three times that to Denver, Colorado, for example, but I would say Wyoming borders Montana about as much as it borders Colorado)

Average distance of all pairs of points in the two states (hm, maybe not. That could behave weirdly for states that aren’t very ‘compact’) or geometric mean of the fraction of a state’s border shared with the neighboring state would be fairer. Or maybe, the geometric mean of the fraction of the area of State S is closest to state T and the fraction of the area of state T that is closest to S?

Alternatively, make the states clusters, add all cities on highways as vertices, and use highways stretches between cities as edges.

Byte Magazine had an article in 1986 that drew the US based on distances between cities. https://archive.org/details/byte-magazine-1986-08/page/n103/...

I wonder whether adding Canada and Mexico as nodes would "improve" some of the first few graphs.

This map makes it clear that it's New York, not Pennsylvania, which is the keystone state.

It also makes you google why St. Louis lost out to Chicago.

Weird that it plots a planar graph in a slightly non-planar way in the northeast.

Force-directed layout has no guarantees that a planar graph will be drawn planar. It often comes out that way, given how the algorithm works, but not always. Especially nodes that are "trapped" between others may have trouble "escaping" to the other side of an edge at times, due to the forces involved.

It may help increasing the dimensions for Graphviz (I think its force-directed layout can work in up to 10 dimensions), but there's still a step involved that projects everything to 2D in the end, so it might still happen.

Yes, force-directed layout doesn't consider number of crossings. dot is the only graphviz program that reduces crossings, and because of the level assignment constraint, even small graphs like K_4 or K_2,2 have crossings that could be avoided by just routing edges differently.

Yes, you can set NDim, https://graphviz.org/doc/info/attrs.html#d:dim I'm not sure why we said up to 10. It's hard to see even in 8 dimensional space!

In terms of drawing graphs of the U.S. states or data like that, it should be possible to, say, create a point at the centroid of every region, then connect the adjacent regions to form a mesh, then feed the mesh to neato with some options to relax the layout but retain the mesh. This is what the overlap removal algorithm does anyway. See https://www.graphviz.org/Documentation/GH10.pdf, at least the figures.

There's plenty of recent work that improves on some of the graphviz algorithms. It's a pity that without a convenient way to incorporate such inventions in a larger system, it tends to languish and not have as much impact or isn't easily available to people that could use it. Nocaj/Ortmann/Brandes work on untangling hairballs is another example: http://jgaa.info/accepted/recent/NocajOrtmannBrandes.pdf We even have this prototyped in a directory somewhere but it would be more work to merge it into the release.

hmm if the layout system had edge weights representing distance btwn centroids, this would be pretty exact with not that much extra information

Reply on news.ycombinator.com