A block-cut tree, also called a block-cutpoint tree or BC-tree, of a connected graph
is the bipartite graph whose graph
vertices consist of one block node for each block of
and one articulation-vertex node for
each articulation vertex of
. A block node and an articulation-vertex node are adjacent
vertices if the corresponding block contains the corresponding articulation
vertex (Harary and Prins 1966).
The resulting graph is a tree. If is a biconnected graph,
its block-cut tree consists of a single block node. For a disconnected
graph, the same construction gives a block-cut forest, one tree for each connected
component. Every tree leaf of a nontrivial block-cut
tree is a block node, so the graph distance between
every pair of tree leaves is even. Conversely, every
tree in which the graph distance
between every pair of tree leaves is even is the block-cut
tree of some connected graph (Harary and Prins
1966).
The blocks and articulation vertices, and hence the block-cut tree, can be found in time using a depth-first
traversal. The block-cut tree should not be confused with a block
graph, which is a graph in which every block is a complete
graph.
The block-cut tree decomposes a connected graph at its vertex cuts of size 1. The analogous decomposition of a biconnected graph at its vertex cuts of size 2 is represented by an SPQR tree.