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.
