It's really common for star maps to be in 2D. I think this is unfortunate, so I'd like to talk about making the transition to a 3D star map.
The difficulty in a 3D star map is that the human mind really tends to think of surfaces rather than freefloating objects. Just look at how difficult it is to make out what is going on when looking down on scaffolding: how many levels high is it? Which slats are on which levels? This is a problem that many games are beginning to encounter as they try to build very high (tall) levels. Mirror's edge has some examples, as does Prince of Persia: it's easy to lose track of what is "beneath" you, even though you passed through a few moments ago. Which part of the level is that, down there?
And those games have it easy, because at least they're working with surfaces. A star map is just points of light.
There are several things we can do to ease the problems.
One is to introduce surface-like elements, including things like radial disks around certain stars, and trade routes that have broad, flat surfaces. It's critical to keep these things to a size that can be easily extrapolated, so you can tell the distance. Having a disk around a star that grows based on population makes it impossible to use that disk to determine what z-level the star is on. If the disk is always the same size, though, we can guess where the star is by looking at the perspective-induced difference is size.
Having a flat "z-surface" with "raised lines" is pretty common in games. This is descended from old submarine sims. I find this to be a pretty poor solution, only slightly better than no marks at all. A single flat surface with no relation to any of the actual points of light isn't a very useful surface, so the surfaces should integrate the stars.
Gently sliding the camera into position rather than simply "popping" into place is also somewhat useful, as it gives parallax information. This only works until the user switches screens due to the way we process visuals, so it might be useful to slide the camera into place every single time the user switches screens, even if the galactic camera has no reason to have moved. Even a tiny motion is sufficient to give parallax.
Keeping the same "up" and "north" is also useful. It's tempting to let the player control the pitch and yaw of the camera, since it's a 3D world and your instincts are based around flight sims and FPS games. But in actuality the only control the player needs is zoom: always keeping the same up, down, north, south, east, and west means that the players will be able to memorize the location of stars using the same faculties they use to memorize the location of the door in their room, an icon in their desktop, the shift stick in their car. Humans are bad at rotational pattern recognition, and there's no gameplay reason to allow rotation.
All of these will help, but they have the fundamental problem that they're still representing freefloating dots and rails rather than surfaces. It might be worthwhile to create surfaces instead. We can, for example, build a number of surfaces into the star region, and stars have to be on a surface. Due to the vertical requirements, the best solution is probably thick tubes or large freefloating objects instead of a terrain-like surface.
You will have problem with opacity, though: how will you see stars on the opposite side of an object, or occluded by an object? On the plus side, your travel routes could be inherently linked to the topology, making it feel like more than just a visual aide.
This brings up the problem of opacity in general. Stars are not the only things in space. Things like nebulae are often important tactical considerations, but rendering them is difficult to do without mucking up the display: large opaque blobs will hide everything inside them or on the other side. Also, since they are arbitrarily sized and shaped, it can be very hard to determine where in space they actually are.
National borders have the same problem: they are a 3D perimeter of arbitrary size and shape. How do you draw them so they don't confuse the viewer or obscure other important things? Transparency might seem like the answer, but in fact it just makes things even muddier.
I don't know if there's a perfect solution, but I'm playing with two solutions.
One uses the "stars on surface" approach as mentioned above, except that the "surface" is automatically generated to include all stars not part of your nation/reach. This essentially puts your nation inside a bubble. This has a lot of downsides, though. It requires that you have "flight sim" controls due to opacity issues, which in turn means that if your nation is larger than about a dozen stars, you start losing track and thinking of them as "those stars" rather than individual stars.
The other idea is the "panned opacity". I think of this like radar: the opaque walls of nebula and borders are drawn, but only in a transitory thin slice as the "scanner" travels. This seems to work okay, but it feels kind of "foggy".
None of this is necessary if you have a surfaced-based space, though: you can just color the always-visible surfaces the color of their owners.
Another "solution" is to simply radically downplay the importance of the 3D star map to the player. The AI can take advantage of that 3D space to build an interesting world, but the player's game takes place in a small enough region that he can't get lost. Also, if the player is an avatar instead of a nation, the player will have an easier time of it because they won't have to remember where every star is and what they are doing, just two or three.
What are your opinions on 3D star maps?