Biconnected component

The classic sequential algorithm for computing biconnected components in a connected undirected graph is due to John Hopcroft and Robert Tarjan (1973).

This property can be tested once the depth-first search returned from every child of v (i.e., just before v gets popped off the depth-first-search stack), and if true, v separates the graph into different biconnected components.

Note that the terms child and parent denote the relations in the DFS tree, not the original graph.

The list of cut vertices can be used to create the block-cut tree of G in linear time.

In the online version of the problem, vertices and edges are added (but not removed) dynamically, and a data structure must maintain the biconnected components.

Uzi Vishkin and Robert Tarjan (1985) [5] designed a parallel algorithm on CRCW PRAM that runs in O(log n) time with n + m processors.

The subgraphs formed by the edges in each equivalence class are the biconnected components of the given graph.

An example graph with biconnected components marked
Each color corresponds to a biconnected component. Multi-colored vertices are cut vertices, and thus belong to multiple biconnected components.
A demo of Tarjan's algorithm to find cut vertices. D denotes depth and L denotes lowpoint.
A graph, and its block-cut tree.
Blocks :
b 1 = [1,2]
b 2 = [2,3,4]
b 3 = [2,5,6,7]
b 4 = [7,8,9,10,11]
b 5 = [8,12,13,14,15]
b 6 = [10,16]
b 7 = [10,17,18]
Cutpoints:
c 1 = 2
c 2 = 7
c 3 = 8
c 4 = 10