I think a bunch of them are force-arranged. The early map types ("simple"?) are just "randomly select two systems and connect them, repeat until fully connected."

I doubt so because I ran tests with graphviz and the "randomly pick two" is (1) a nightmare to balance because the slightest modification of the probability immensely affects the graph and (2) AIW's simple graph is planar and very good looking. I was thinking of something like "give vertices random coordinates* and link them to their nearest neighbors without crossing an already made link** and without making links longer than X."

** but sometimes "simple" galaxies are a rarely a bit tangled.

* elegantly spreading dots on a 2D plan would be made with a "scrambled grid", but AIW's "simple" has too many holes (which is good for a strategy and gameplay standpoint).

Also, the "random pairs" make "logical" graphs that need to be displayed and untangled. "Tree" and "Snake" look like that, but "Simple" and "Lattice" don't: they're already untangled. That's why I think the later's vertices are first spread on a 2D plane and linked with their neighbors.

However, "Snake" is a very interesting case: it has some local "neighboring" pairing but some seemingly random "jumps" that look more like "Tree". My bet is that the algo recursively links a vertex with

*the* nearest (unlinked) vertex, which cause the string to "jump" when there is no more unlinked vertices near. But looking more at it, it appears this isn't the case: just take one end or the other of the snake and see if the next star is the nearest; sooner or latter you'll see a "better choice" when the string "jumps" away.

Anyway.

I'm really curious about this and would much appreciate the least hint from Arcen.