Profiles of separations: in graphs, matroids and beyond

Abstract

We show that all the tangles in a finite graph or matroid can be distinguished by a single tree-decomposition that is invariant under the automorphisms of the graph or matroid. This comes as a corollary of a similar decomposition theorem for more general combinatorial structures, which has further applications. These include a new approach to cluster analysis and image segmentation. As another illustration for the abstract theorem, we show that applying it to edge-tangles yields the Gomory-Hu theorem.

33 pages

References in corpus (1)

• Connectivity and tree structure in finite graphs

Cited by in corpus (10)

• Connectivity and tree structure in finite graphs
• Tangles and the Mona Lisa
• Computing with Tangles
• $k$-Blocks: a connectivity invariant for graphs
• Tangled up in Blue (A Survey on Connectivity, Decompositions, and Tangles)
• Canonical tree-decompositions of finite graphs II. Essential parts
• On the Medianwidth of Graphs
• Unifying duality theorems for width parameters in graphs and matroids. II. General duality
• Canonical tree-decompositions of finite graphs I. Existence and algorithms
• Edge-connectivity and tree-structure in finite and infinite graphs