Lets assume for a moment that we will be dealing with something like 100-200 thousand star systems. Each important system will have data about what is there, but lets ignore that for now.
Looking at the star maps in Project Rho, it's my feeling that much more than 30-40 stars in a single map of 3D space projected onto 2 dimensions is pushing the boundaries of human comprehension. It is also a requirement here that we use flat 2-D images - I am not making assumptions about technology available to players or readers. Really, some level of the presentation would have to work as a map in a printed book.
With say 150K objects, splitting them up into "subsectors" of average 30 systems each, we would be talking 5000 individual subsector maps - it it were all cubical, then 17x17x17 subcubes. Of course, we don't want to issue players with a 5000 page atlas to try to work their way around. We can generate any where we really need detail on the fly, but we need top-level maps.
courtesy of the CIA. What does it tell us? Well, quite a lot. It shows centres of population, oceans and land, mountains and rivers (strategically significant since they constrict and direct movement) political boundaries and relative national sizes.
All the key stuff, strategically. We can get a rough approximation of travel times, of constricting terrain, of key objectives and obstacles. If it were 1944, you can't plan D-day from it, but you can get a pretty good idea of the progress of the liberation of Europe. It excludes, but could add, symbols for transportation routes, industrial and resources regions, and lots of other types of data.
So, for our star map, what sort of data could be displayed? Well, the simplest thing is Polity capitals. Transportation routes (with width indicating flow volume and color indicating polity) are another.
For multiple polities it might be too dense, but the boundaries of a single species could be shown by all the systems with worlds inhabited by that species. Or if we consider a graph of a Delaunay tessellation in three dimension of all stars controlled by an empire, we could display small dot in the middle of a line connecting a controlled start with an uncontrolled. This also bring up a question of what might constitute "controlled" or "inside a sphere of influence. Good thing Graph Theory is fun.
were used to describe routes in Europe from at least the 16th century. The advantage of the strip map is that not only does it show the core route, but it also gives diversions from the route. This could be useful for a planner who had developed a core approach, but wanted to look at local alternatives to avoid particular problems. This sort of data could be presented as a 3-d map or as a classic shape and line graph - which in fact is what a road map is.
Anyway, quite a few ideas to try -- I must get back to that star data -- but I am open for more suggestions.