I'm worried that part of the mechanisms gets forgotten, but when Destroyer of Worlds came out, it introduced an interesting feature (two, actually).
1)
Edges can change. With the nomad planets, the wormhole links between the planets were able to change. That induced a redefinition of wormholes (entry points of wormhole links) as game objects that can open, close and move. I feel that hasn't been exploited enough yet and I hope that will be subject to mods because I really want to make
that idea.
2)
Vertices can disappear. The Nomad Beacon had the ability to destroy one planet (technically, remove one vertex from the graph), but with constraints: the graph must still be in one piece (or then,
deus ex machina, didn't happen). That was to ensure the AI navigation logic can always find a path between any pair of planets in the galaxy.
I would love to see these mechanisms refined, especially the AI navigation logic, allowing it to handle unreachable destinations for temporally closed wormholes. For instance, I would love to see special galaxies with several separated pieces requiring the passage of a nomad planet to briefly (one to some hours) connect the parts. (The intragalactic warp gates would sure have some uses with that.) Or more simply, periodically closing/reopening wormholes. It would also be possible to expand on player's agency on the galactic map: more striking than a gate raid, the definitive closure of a wormhole link. Or the creation of a shortcut! (I might post that into "Latter Ideas".)
TL;DR:
Don't forget to let wormhole mechanisms moddable.
Is an improvement to let AI understand temporal unreachability feasible?