The major constraints of your problem are twofold: creating a 1-connected graph; and creating it with proximal connections. Philip's answer, while somewhat valuable, does not address all constraints of your problem
Ideally, a wormhole should not exceed a maximum length and if
possible, wormholes should not cross each other.
When you naively connect points in a cloud, you run the risk (and a high one, at that) of these conditions not being fulfilled.
So you see, the problem isn't so much one of connectivity as one of proximity on those connections. It is trivial to connect every node in a graph to every other node, but connecting only to those that are closest while maintaining 1-connectedness of the overall graph is a bit more tricky.
This is what a Delaunay triangulation creates, in n dimensions. The first reason to use Delaunay triangulation is that it fulfills both of these implicitly. The second reason is that it is far easier to work backwards from such a graph (subtracting edges and vertices you don't want), than to try to create it in other ways.
- Randomly create your full point cloud.
- Delaunay-triangulate it.
- Construct the graph (connection of points). In this, you can either generate the whole graph (every star) first, and then derive graph as minors representing your wormhole-connected regions, when performing step 4. Alternatively you can work the other way around, generating only the wormhole-connected regions first as supergraph nodes, and then in a second phase, generate individual stars within those regions' bounding volumes (for these I would derive the Delaunay triangulation's graph dual -- the Voronoi diagram in 3 dimensions) as subgraphs. Now you have proximally-connected star clusters, and all clusters are connected by rarer wormholes: your topology and topography make sense to the player.
- Apply intelligent methods to shape the super- and subgraphs, depending on how you've chosen to treat it in step 3.
It's important to see that this is a hierarchical process. The first level deals with wormhole connectivity; the second deals with distances presumably traversable using a standard ship drive. You can apply Delaunay at one or both levels to satisfy your constraints.
Doing this purely topologically will leave you with wormholes that don't make sense, since they might connect one side of the galaxy to another, in spite of a high density of stars in beween (and perhaps even falling on the wormhole's direct route). Topology is not topography; the latter is a consideration over and above the former. You are concerned with proximity and thus topography.