CODEWITHSUNDEEP
graphgraph-theorygraph-algorithm
Kumalh
Kumalh

Reputation: 539

Generating random biconnected graph

Is there a straightforward algorithm for generating a random undirected biconnected graph (given a number of vertices as input)? I understand how to determine if a given graph is biconnected, but I'm struggling to generate one programatically.

Upvotes: 6

Views: 629

Answers (2)

dingalapadum
dingalapadum

Reputation: 2177

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) pairs of vertices (i.e possible edges) 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...)

Upvotes: 4

MT0
MT0

Reputation: 167981

A simple way to is to create a random maximal planar (tri-connected) graph:

  • Start with 3 vertices connected in a cycle which forms 2 triangular faces (interior and exterior of the cycle).
  • To add each subsequent vertex pick a random face and trisect it with a vertex and 3 edges.

You could stop here - since the graph is tri-connected it is also bi-connected.

However, if you want to remove edges and ensure that you still have a biconnected graph then only remove edges where both incident vertices are degree 3-or-more and test each edge prior to removal using Hopcroft & Tarjan's Depth-First Search Algorithm to find Biconnected Components to check for biconnectivity without that edge.

Note - this will always create a planar graph.

Upvotes: 0

Related Questions