Biconnected component
[Image:Graph-Biconnected-Components.svg|thumb|alt=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.]
In graph theory, a biconnected component or block is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks are attached to each other at shared vertices called cut vertices or separating vertices or articulation points. Specifically, a cut vertex is any vertex whose removal increases the number of connected components. A block containing at most one cut vertex is called a leaf block, it corresponds to a leaf vertex in the block-cut tree.
Algorithms
Linear time depth-first search
The classic sequential algorithm for computing biconnected components in a connected undirected graph is due to John Hopcroft and Robert Tarjan. It runs in linear time, and is based on depth-first search. This algorithm is also outlined as Problem 22-2 of Introduction to Algorithms.The idea is to run a depth-first search while maintaining the following information:
- the depth of each vertex in the depth-first-search tree, and
- for each vertex, the lowest depth of neighbors of all descendants of in the depth-first-search tree, called the.
The key fact is that a nonroot vertex is a cut vertex separating two biconnected components if and only if there is a child of such that. This property can be tested once the depth-first search returned from every child of, and if true, separates the graph into different biconnected components. This can be represented by computing one biconnected component out of every such, and then erasing the subtree of from the tree.
The root vertex must be handled separately: it is a cut vertex if and only if it has at least two children in the DFS tree. Thus, it suffices to simply build one component out of each child subtree of the root.
Pseudocode
GetArticulationPointsvisited := true
depth := d
low := d
childCount := 0
isArticulation := false
for each ni in adj do
if 'not visited then
parent := i
GetArticulationPoints
childCount := childCount + 1
if low ≥ depth then
isArticulation := true
low := Min
else if ni ≠ parent then
low := Min
if or then'
Output i as articulation point
Main
GetArticulationPoints // r is an arbitrary root
Note that the terms child and parent denote the relations in the DFS tree, not the original graph.
Other algorithms
A simple alternative to the above algorithm uses chain decompositions, which are special ear decompositions depending on DFS-trees. Chain decompositions can be computed in linear time by this traversing rule. Let be a chain decomposition of. Then is 2-vertex-connected if and only if has minimum degree 2 and is the only cycle in. This gives immediately a linear-time 2-connectivity test and can be extended to list all cut vertices of in linear time using the following statement: A vertex in a connected graph is a cut vertex if and only if is incident to a bridge or is the first vertex of a cycle in. The list of cut vertices can be used to create the block-cut tree of in linear time.In the online version of the problem, vertices and edges are added dynamically, and a data structure must maintain the biconnected components. Jeffery Westbrook and Robert Tarjan developed an efficient data structure for this problem based on disjoint-set data structures. Specifically, it processes vertex additions and edge additions in total time, where is the inverse Ackermann function. This time bound is proved to be optimal.
Uzi Vishkin and Robert Tarjan designed a parallel algorithm on CRCW PRAM that runs in time with processors.
Related structures
Equivalence relation
One can define a binary relation on the edges of an arbitrary undirected graph, according to which two edges and are related if and only if either or the graph contains a simple cycle through both and. Every edge is related to itself, and an edge is related to another edge if and only if is related in the same way to. Less obviously, this is a transitive relation: if there exists a simple cycle containing edges and, and another simple cycle containing edges and, then one can combine these two cycles to find a simple cycle through and. Therefore, this is an equivalence relation, and it can be used to partition the edges into equivalence classes, subsets of edges with the property that two edges are related to each other if and only if they belong to the same equivalence class. The subgraphs formed by the edges in each equivalence class are the biconnected components of the given graph. Thus, the biconnected components partition the edges of the graph; however, they may share vertices with each other.Block graph
The block graph of a given graph is the intersection graph of its blocks. Thus, it has one vertex for each block of, and an edge between two vertices whenever the corresponding two blocks share a vertex.A graph is the block graph of another graph exactly when all the blocks of are complete subgraphs. The graphs with this property are known as the block graphs.