How to generate random connected planar graph?

Question

I was trying to generate random connected planar graph for dome numerical experiment of some transportation problem. I have three types of nodes: supply, transshipment and demand. I have the number of nodes and edges; also, i have following rules:

1. There is no arc from supply nodes driectly to demand nodes. The connection between these two must be through transshipment nodes.
2. It must be a connected graph.
3. The grapgh can be either directed or undirected.
4. Total number of edges is given, but there is no specific rule about exact number of edges between different types of nodes.
5. There are no edges between supply nodes; however, it is not the case for transshipment and demand nodes. Any ideas how to code it? (no matter in what language, i just want to have an understanding of the process)

Thanks

Answer 1

Here are two approaches, both for an undirected graph (but easily modified to handle a digraph).

Method 1: Start with a complete graph (in the sense that all legal edges exist). Compile a list of all edges and shuffle it randomly. While the number of edges exceeds your quota, pop the next edge and remove it. If the graph remains connected, continue; if not, replace the edge and continue. If you use up all the edges before reaching the target number of edges, start over with a new random seed.

Checking whether the graph remains connected after removing edge (i, j) is not as bad as it sounds. You just need to do a depth-first search for a surviving path from i to j.

Method 2: Write an integer linear program to selected a subset of $m$ edges such that the graph is connected ($m$ being your required edge count). The model will contain a binary variable for each edge. Assign each of those variables a randomly generated positive cost and set minimization of the total cost as the objective. Method 2 does not require restarts (unlike method 1), but does require an integer programming solver and is likely to be slower (possibly a lot slower).