Biconnected component

Maximal biconnected subgraph

In graph theory, a biconnected component (sometimes known as a 2 connected component) 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 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 C be a chain decomposition of G. Then G is 2 vertex connected if and only if G has minimum degree 2 and is the only cycle in C. This gives immediately a linear time 2 connectivity test and can be extended to list all cut vertices of G in linear time using the following statement: A vertex v in a connected graph G (with minimum degree 2) is a cut vertex if and only if v is incident to a bridge or v is the first vertex of a cycle in 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. Jeffery Westbrook and Robert Tarjan (1992) developed an efficient data structure for this problem based on disjoint set data structures. Specifically, it processes n vertex additions and m edge additions in O(m α(m, n)) total time, where α is the inverse Ackermann function. This time bound is proved to be optimal. Uzi Vishkin and Robert Tarjan (1985) designed a parallel algorithm on CRCW PRAM that runs in O(log n) time with n + m processors.

One can define a binary relation on the edges of an arbitrary undirected graph, according to which two edges e and f are related if and only if either 1=e = f or the graph contains a simple cycle through both e and f. Every edge is related to itself, and an edge e is related to another edge f if and only if f is related in the same way to e. Less obviously, this is a transitive relation: if there exists a simple cycle containing edges e and f, and another simple cycle containing edges f and g, then one can combine these two cycles to find a simple cycle through e and g. 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.

The block graph of a given graph G is the intersection graph of its blocks. Thus, it has one vertex for each block of G, and an edge between two vertices whenever the corresponding two blocks share a vertex. A graph H is the block graph of another graph G exactly when all the blocks of H are complete subgraphs. The graphs H with this property are known as the block graphs.

A cutpoint, cut vertex, or articulation point of a graph G is a vertex that is shared by two or more blocks. The structure of the blocks and cutpoints of a connected graph can be described by a tree called the block cut tree or BC tree. This tree has a vertex for each block and for each articulation point of the given graph. There is an edge in the block cut tree for each pair of a block and an articulation point that belongs to that block.