Bounded-diameter tree-decompositions

DOI10.1007/S00493-024-00088-1MaRDI QIDQ6548028FDOQ6548028

Authors: Eli Berger, Paul Seymour 

Publication date: 31 May 2024

Published in: Combinatorica (Search for Journal in Brave)

Recommendations

• scientific article; zbMATH DE number 1222605
• Tree-decompositions with bags of small diameter
• Bounding connected tree-width
• Connected tree-width
• On the tree-width of planar graphs

zbMATH Keywords

geodesictree-decompositionquasi-isometrytree-widthtree-lengthadditive distortiondiameter-width

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph representations (geometric and intersection representations, etc.) (05C62) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Graph minors. V. Excluding a planar graph
• Constructing group actions on quasi-trees and applications to mapping class groups
• Geometry of pseudocharacters.
• Additive Tree Spanners
• Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs
• Tree-decompositions with bags of small diameter
• Tree approximation in quasi-trees
• Connected tree-width
• Towards tight(er) bounds for the excluded grid theorem
• Tree-chromatic number
• Acylindrical group actions on quasi-trees
• Polynomial bounds for the grid-minor theorem

This page was built for publication: Bounded-diameter tree-decompositions

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