I believe a "random" or grid pattern is the most fun - in this, you can represent all of the systems on a grid (one system at each point, note that it doesn't have to be a grid when you make a pretty map for the player to see, it's just that every system connect to up to four others) and the player travels around them freely. Perhaps the player is trying to find the Heretic system (which is placed randomly on the fringes of the map), looking for clues along the way. After all, the last thing the CW wants is angry aliens knocking on their door - they don't have any reason to spread it's location around and it may have been forgotten.
There are a few ways to do this.
The structure of Transcendence as it is currently requires a pattern that is at least semi linear, with a definable direction and little backtracking. It is boring to be in systems where you have already been because they are empty. You don't live in the Transcendence universe, it lives around you and you destroy it as you go along.
Thus a random or grid pattern will not work well because when the player moves though areas he has already been to it will be somewhat boring and also serve to further highlight the implausibility of a single ship laying waste to entire systems.
You can fake it, have the general layout of systems designed by hand and remain constant (this is how it is now actually except that the map is just a line of gates). For example eridani will be on one side of "pirate territory" from St. K's, and heretic is on the other side of slaver and ares territory from st. ks. This provides a sense of directionality, allowing the difficulty to ramp up as the player gets farther into the game.
I have a map of this kind of system here. The player starts at eridani and his only choice is to move through pirate controlled territory to St. K's. When I say "pirate territory" I mean exactly like early game is now, not ONLY pirates. All of the red systems will have early game enemies in them .
The player will go through these and end up in CW space (signs and game hints lead them there, as well as harder systems acting like a wall) there are only a few worlds here as they will mostly be pretty boring, devoid of enemies. St. K's is here too.
The sections marked 'Frontier' are midgame systems like those right after St. K's. Those marked "final frontier" are harder, progressing in difficulty as they approach the bottom of the map. Late game is all the systems at the bottom.
Heretic oculd be anywhere in late game space, hence the HERETIC? labels. Still it should be kind of out of the way. If you really want to force the player to not be able to find it without getting the "clues" you can go all twisty little passages with a maze of Elysium systems (each gate leads to another elysium ad infinitum unless you know where you're going). Even if that isn't part of the endgame it woudl make a neat cursed gem of despair.
You'll note some systems are marked with X's. This is possible places to put "plot points" (which can also be random - I think Charon should be hidden in a random spot, befitting an outlaw hideout). Plot points can be clues to the location of Heretic or something more cliche like pieces of the control rod. They could also be unrelated to the main goal (you could track down the Charon system based on some hints at a bar just for the loot).
The plot points (and the search for heretic) encourage players to explore more thoroughly - otherwise they might feel like they were just aimlessly wandering - since going directly to heretic can't be safely done until the player is stronger, and having access to Ares space (you could technically go there far before you were ready) but not being allowed in (because you're weak) makes all you do seem like leveling up (boring) when it should be a journey.
However, though a stargate network really isn't an easy add - it's not just throwing in more gates. You'd need a galaxy map or you'd get hopelessly lost (even with signs - this isn't a text adventure, please don't make me write on a piece of paper). You'd need a news service or expanded tavern rumor system or equivalent to tell the player where to go (and where NOT to go, as it's pretty easy to wander off into slaver space as the fifth system you visit). You'd need a solution to the empty system problem posed earlier.
At least for the empty systems (as well as the destroy the universe thing) there are two semi-ridiculous options.
1. Basically you'd take all the stations as they are now, and call them less dramatic things. Outposts, guard/sentry posts/platforms, etc. Why? Because they're no longer the center of power in systems, they just represent occupation of systems. No, in systems that are really under control by sovereigns (home worlds, front lines, frequently traveled systems) there are HUGE bases that the player has no chance of deafeating directly. The player is not even encouraged or required to defeat them. In fact it should be basically impossible. Ares space is Ares controlled and if the entire CW fleet can't take it away from them how can one ship? You should never be safe in an enemy system. As long as these huge stations exist, the outposts will respawn in a limited fashion. There can be missions to take these down (think communes) or scripted events where systems change hands while you watch (or participate), and theoretically the player could do it but in general they should just remain - such things are beyond a single person.
2. To be honest I forgot number two.
It's late... If I remember I'll post it tomorrow.
It's pretty easy to do. I know other people have done a lot with this also.
