I'm trying to find an efficient algorithm to generate a simple connected graph with given sparseness. Something like:
Input:
N - size of generated graph
S - sparseness (numer of edges actually; from N-1 to N(N-1)/2)
Output:
simple connected graph G(v,e) with N vertices and S edges
For each node you need at least one edge.
Start with one node. In each iteration, create a new node and a new edge. The edge is to connect the new node with a random node from the previous node set.
After all nodes are created, create random edges until S is fulfilled. Make sure not to create double edges (for this you can use an adjacency matrix).
Random graph is done in O(S).