Tangles and connectivity in graphs

DOI10.1007/978-3-319-30000-9_2MaRDI QIDQ2798707zbMATH OpenOpenAlexFDO

Authors Martin Grohe

Publication date 13 April 2016

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

connectivity systemsstructural graph theory

Mathematics Subject Classification ID

Connectivity (05C40) Graph theory (including graph drawing) in computer science (68R10)

Abstract: This paper is a short introduction to the theory of tangles, both in graphs and general connectivity systems. An emphasis is put on the correspondence between tangles of order k and k-connected components. In particular, we prove that there is a one-to-one correspondence between the triconnected components of a graph and its tangles of order 3.

Recommendations

• Computing with tangles
• Computing with Tangles
• Tangles, trees, and flowers
• Rooted grid minors
• Tangles are Decided by Weighted Vertex Sets

Cited in

(11)

• Unravelling tangled graphs
• Tangle and Maximal Ideal
• Rooted grid minors
• Tangles and single linkage hierarchical clustering
• Tangles are Decided by Weighted Vertex Sets
• Ends, tangles and critical vertex sets
• Computing with tangles
• Computing with Tangles
• The structure of quasi-transitive graphs avoiding a minor with applications to the domino problem
• Characterising 4-tangles through a connectivity property
• A structural approach to tree decompositions of knots and spatial graphs

This page was built for publication: Tangles and connectivity in graphs

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