Generating random biconnected graph

You can do a very simple probabilistic approach:

1. Create an empty graph with n nodes
2. For each pair of nodes:
 -Flip a fifty-fifty-coin to decide whether to put an edge in there or not

You have O(n^2) pair of vertices and this will also be the expected running time of this algorithm, since the random graph generated by this procedure will be bi-connected with high probability.

Hence, in the end to make sure your graph really is bi-connected you just run the regular procedure which you already know.

For the (very unlikely) scenario where the check returns "graph is not bi-connected", just repeat the procedure.

The really intriguing question is "why will I get a biconnected graph w.h.p.?". I will omit the formal proof which is a bit tedious and by how you are asking, I assume you just want something that works and you don't care too much about why it works. If I'm wrong and you actually need a proof I suggest you either ask on mathoverflow or you drop me a comment - maybe I'll try to make it formal if I find the time.

For the moment, just to give you an intuition for why this will work, consider the following approach of how a proof could go:

• Note that the number of graphs which is not bi-connected is equal to the number of graphs with at least one articulation-vertex.

• Let us roughly compute the probability of a single vertex of being an articulation point: The idea is that if v is an articulation vertex then it splits the n vertices into two disjoint sets of size k and n-k such that there is no edge between those sets. Now intuitively it should be more or less clear that k*(n-k) coin flips which all have to result in "no-edge" is not very probable (basically (1/2)^(k*(n-k))). We still have to multiply by n (since for each node) but this will still not make a significant difference, and as you might see now it is very unlikely for graph with large enough 'n' to not being bi-connected.

(What's still missing is to consider "for each possible partitioning", i.e. for the different choices of k, and then maybe be more careful since it would actually be ((n-1)-k) and k, rather than (n-k) and k because the vertex under consideration is not part of any of the 2 sets... I'm just saying these things to illustrate the kind of details one would still have to worry about for a formal proof...)