Computing with Tangles

DOI10.1145/2746539.2746587MaRDI QIDQ5892103zbMATH OpenOpenAlexFDO

Authors Martin Grohe, P. Schweitzer

Publication date 21 August 2015

Published in Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.00190

zbMATH Keywords

connectivity functiondecompositionstangles

Mathematics Subject Classification ID

Connectivity (05C40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Abstract: Tangles of graphs have been introduced by Robertson and Seymour in the context of their graph minor theory. Tangles may be viewed as describing "k-connected components" of a graph (though in a twisted way). They play an important role in graph minor theory. An interesting aspect of tangles is that they cannot only be defined for graphs, but more generally for arbitrary connectivity functions (that is, integer-valued submodular and symmetric set functions). However, tangles are difficult to deal with algorithmically. To start with, it is unclear how to represent them, because they are families of separations and as such may be exponentially large. Our first contribution is a data structure for representing and accessing all tangles of a graph up to some fixed order. Using this data structure, we can prove an algorithmic version of a very general structure theorem due to Carmesin, Diestel, Harman and Hundertmark (for graphs) and Hundertmark (for arbitrary connectivity functions) that yields a canonical tree decomposition whose parts correspond to the maximal tangles. (This may be viewed as a generalisation of the decomposition of a graph into its 3-connected components.)

Recommendations

• Computing with tangles
• Computing with colored tangles
• Computing with knot quandles
• The complexity of finding tangles
• Computing height-optimal tangles faster
• EMBEDDING TANGLES IN LINKS
• Computing with Böhm trees
• Tangles and connectivity in graphs
• Computing spin networks

Cites work

• Approximate distance oracles
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast C-K-R partitions of sparse graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On approximate distance labels and routing schemes with affine stretch
• On sparse spanners of weighted graphs
• Ramsey partitions and proximity data structures
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Shortest-path queries in static networks

Cited in

(10)

• Tangles and connectivity in graphs
• Tangle and Maximal Ideal
• Rooted grid minors
• Tangles and single linkage hierarchical clustering
• Refining a tree-decomposition which distinguishes tangles
• Computing with tangles
• Tangle bases: Revisited
• The complexity of finding tangles
• Point sets and functions inducing tangles of set separations
• Connectivity functions and polymatroids

Describes a project that uses

Uses Software

• Graphs

This page was built for publication: Computing with Tangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5892103)