Treewidth of graphs with balanced separations

DOI10.1016/J.JCTB.2018.12.007MaRDI QIDQ2312607zbMATH OpenOpenAlexWikidataFDO

Authors 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)

Abstract: We prove that if every subgraph of a graph $G$ has a balanced separation of order at most $a$ then $G$ has treewidth at most $15a$. This establishes a linear dependence between the treewidth and the separation number.

Recommendations

• On balanced separators, treewidth, and cycle rank
• Parameters tied to treewidth
• Treewidth for graphs with small chordality
• Partitioning graphs of bounded tree-width
• Treewidth reduction for constrained separation and bipartization problems

Cites work

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

Cited in

(21)

• Subexponential-time algorithms for finding large induced sparse subgraphs
• Intersection graphs of orthodox paths in trees
• Constant threshold intersection graphs of orthodox paths in trees
• Treewidth of graphs with balanced separations
• Graphs of linear growth have bounded treewidth
• Beyond outerplanarity
• Balanced trees with removals: An exercise in rewriting and proof
• On balanced separators, treewidth, and cycle rank
• Product structure extension of the Alon-Seymour-Thomas theorem
• Notes on graph product structure theory
• Balancing Bounded Treewidth Circuits
• A note on sublinear separators and expansion
• Balancing bounded treewidth circuits
• Pursuit-evasion in graphs: zombies, lazy zombies and a survivor
• Structure of graphs with locally restricted crossings
• Diameter, eccentricities and distance oracle computations on \(H\)-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
• Modularity of minor‐free graphs
• Strongly sublinear separators and polynomial expansion
• On some tractable and hard instances for partial incentives and target set selection
• Orthogonal tree decompositions of graphs
• EPG-representations with Small Grid-Size

This page was built for publication: Treewidth of graphs with balanced separations

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