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.