TOPICS
Search

Block-Cut Tree


A block-cut tree, also called a block-cutpoint tree or BC-tree, of a connected graph G is the bipartite graph whose graph vertices consist of one block node for each block of G and one articulation-vertex node for each articulation vertex of G. 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 G 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 O(|V(G)|+|E(G)|) 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.


See also

Adjacent Vertices, Articulation Vertex, Biconnected Graph, Block, Block Graph, Connected Component, Disconnected Graph, Graph Distance, SPQR Tree, Tree, Tree Leaf, Vertex Cut

Explore with Wolfram|Alpha

References

Harary, F. and Prins, G. "The Block-Cutpoint-Tree of a Graph." Publ. Math. Debrecen 13, 103-107, 1966. https://doi.org/10.5486/PMD.1966.13.1-4.15.Hopcroft, J. and Tarjan, R. "Algorithm 447: Efficient Algorithms for Graph Manipulation." Comm. ACM 16, 372-378, 1973.

Cite this as:

Weisstein, Eric W. "Block-Cut Tree." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Block-CutTree.html

Subject classifications