Depicting the SF sandbox

[thrash]

The essence of a sandbox campaign is that the GM presents (a portion of) the setting to the players and asks, "What do you want to do?" How does this work, however? My question is two-fold:

1. How do you, as the GM, depict a sandbox setting for your players?
2. What do you, as a player, want to see from your GM in a sandbox campaign?

My thoughts are below:

In planet-based settings, which account for most kinds of fantasy, all historical genres, and even the planetary romance side of science fiction, the typical solution is a map. Maps convey a tremendous amount of information -- terrain, points of interest, distances, relationships -- in a compact form, with easily adjustable levels of detail. For a sandbox campaign, a map makes the players' options readily apparent. The answer to "What do you want to do?" becomes "Let's go here."

In a planet-hopping SF setting (including some sorts of paratime travel), the situation is not so simple. First, there is potentially orders of magnitude more information to convey: every one of those destination worlds could (should) offer as much diversity as an entire planet-based campaign, more or less by definition. Second, the information is heavily quantized: the destinations are tightly constrained packets of interest in a vast space of almost literal nothingness. Third, depending on the method of inter-world transportation, the choices of destination may be only loosely (or not at all) constrained by proximity, making option paralysis a real possibility.

In reviewing my library of SF roleplaying games, I've identified four approaches to these problems.

• Create a map anyway. The map could be abstract (Traveller) or realistic (Universe), detailed (Universe, again) or selective (Space Opera). There seems to be a consensus that 20-40 destinations are about right, whether those are confined to a single 8x10 hex array or spread across a cube 200 light-years on a side.
• Provide a network diagram of destinations and their relationships. This is sometimes referred to as a "subway map," and often appears if the chosen mode of transportation (wormholes, jump lines, etc.) depends on defined linkages between nodes. Diaspora represents the low end of this spectrum, with just 2-5 worlds in each network; Thousand Suns recommends the same 20-40 as above. Other examples seem to fall between these extremes. There is also a hybrid case where a map is presented but the choices of destination are constrained to a network by the transportation physics (2300 AD).
• Provide a gazetteer, listing potentially interesting destinations. This frequently occurs where the number of accessible destinations is high, or proximity doesn't matter much (if at all). This is essentially the approach of GURPS Infinite Worlds. If the presented options are few, this shades away from a sandbox campaign into a choose-your-own-adventure plot. Too many options may be just as bad, if the players are unable to process all the information into a decision without GM input.
• Finally, there appears to be a handful of SF RPGs that haven't considered this question at all. I couldn't find a word in Other Suns about mapping its setting, for example. I infer that these either aren't intended for sandbox play (e.g., the GM is expected to present "the planet of the week") or implicitly fall into the gazetteer category (WEG's Star Wars).

Are there other options (or variations) that I've missed? What works? What doesn't?