Tangled up in Blue (A Survey on Connectivity, Decompositions, and\n Tangles)

2016/05/21 by Martin Grohe, Grohe, Martin
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1605.06704

openalex publication_date 2016/05/21 · openalex created_date 2022/09/03 · openalex updated_date 2026/07/28

Abstract

We survey an abstract theory of connectivity, based on symmetric submodular\nset functions. We start by developing Robertson and Seymour's fundamental\nduality between branch decompositions (related to the better-known tree\ndecompositions) and so-called tangles, which may be viewed as highly connected\nregions in a connectivity system. We move on to studying canonical\ndecompositions of connectivity systems into their maximal tangles. Last, but\nnot least, we will discuss algorithmic aspect of the theory.\n

Citations

• Unifying duality theorems for width parameters in graphs and matroids. II. General duality
• Hypertree Decompositions and Tractable Queries
• Tangles and the Mona Lisa
• Isomorphism Testing for Graphs of Bounded Rank Width
• Profiles of separations: in graphs, matroids and beyond

Related

• Computing with Tangles
• Refining a Tree-Decomposition which Distinguishes Tangles
• Tangles and Hierarchical Clustering
• Refining trees of tangles in abstract separation systems: inessential parts
• The Unravelling Problem