From a comment I made: How about using graphvix and in particular dot? Then, all you have to do is to add a layer for the background from any of the large scale images at Hubble.
In dot, you can write something like:
Graph G {
"system A" - "System B" [label='3']
}
This will create an undirected graph with two nodes (system A and system B) linked by an arc labelled 3. Dot will display that network such as the minimal number of arcs cross. It does produce some stunning graphs. Now, it is trivial to read the dot file into python (or c++) and export the shortest path between any two nodes. Note that this is an NP problem so brute force will only work for a small numbers of nodes -- see the travelling sale man problem.
Since dot outputs a png (say), you can edit the image in Gimp. Make the white background transparent. Pick a nice image from Hubble and add it as a layer to your graph image. Make the Hubble image faded so that the graph shows up well. Et voilas, a superb star map with all the needed links.
Note that this could be also used for relationships between NPCs, plot threads, and whatever else that a graph can represent.