random - What is a good method to randomly generate edges between graph nodes?

I am doing a random map generator for a 4X space game.

Each node in the game is place at a random (x,y) coordinate on a 2d grid. A node can have one or more bi-directional edges to another node (representing wormholes). All nodes must have at least one wormhole, and all nodes must belong to the same graph.

Ideally, a wormhole should not exceed a maximum length and if possible, wormholes should not cross each other.

My naive implementation is to iterate through all the nodes and have the node link to the closest 3 nodes. However, I end up with numerous sub graphs. What's a good method to generate the edges for the nodes?

Answer

Here's a good answer to a similar question.

First make a connected graph, perhaps using a minimum spanning tree as in the link above. He suggests using random edge weights to make the "minimum" tree random. Then you can randomly add more edges so it isn't just the minimum tree. How exactly you add the random edges depends on what sort of graph you want.

---

In fact, if the problem is just in making sure the nodes all belong to the same graph, you could take your current method of random generation (or any other), and apply Prim's algorithm on top of it. If you wanted to make minimal changes to the graph just to be sure the subgraphs are all connected, you could set the edge cost to 0 for edges that are already there.