Treewidth of graphs with balanced separations

DOI10.1016/j.jctb.2018.12.007zbMath1416.05089arXiv1408.3869OpenAlexW2963730044WikidataQ128729368 ScholiaQ128729368MaRDI QIDQ2312607

Zdeněk Dvořák, Serguei Norine

Publication date: 17 July 2019

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

treewidthseparators

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12)

Related Items

Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension, Intersection graphs of orthodox paths in trees, Constant threshold intersection graphs of orthodox paths in trees, Structure of Graphs with Locally Restricted Crossings, Modularity of minor‐free graphs, Graphs of linear growth have bounded treewidth, EPG-representations with Small Grid-Size, Beyond Outerplanarity, A note on sublinear separators and expansion, Orthogonal Tree Decompositions of Graphs, On some tractable and hard instances for partial incentives and target set selection, Subexponential-time algorithms for finding large induced sparse subgraphs, Strongly Sublinear Separators and Polynomial Expansion, Notes on graph product structure theory, Treewidth of graphs with balanced separations

Cites Work

• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Graph minors. V. Excluding a planar graph
• Graph minors. X: Obstructions to tree-decomposition
• A partial k-arboretum of graphs with bounded treewidth
• Graph searching and a min-max theorem for tree-width
• Quickly excluding a planar graph
• Treewidth of graphs with balanced separations
• Parameters Tied to Treewidth
• Polynomial Bounds for the Grid-Minor Theorem
• (Almost) Tight bounds and existence theorems for single-commodity confluent flows
• Graph minors. II. Algorithmic aspects of tree-width