Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
From MaRDI portal
Publication:2284742
DOI10.1016/j.jctb.2019.07.007zbMath1430.05123OpenAlexW2968633427MaRDI QIDQ2284742
Yusuke Kobayashi, Ken-ichi Kawarabayashi
Publication date: 15 January 2020
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jctb.2019.07.007
Extremal problems in graph theory (05C35) Graph minors (05C83) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
\(k\)-apices of minor-closed graph classes. I: Bounding the obstructions, Graphs of linear growth have bounded treewidth
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The disjoint paths problem in quadratic time
- Graph minors. XXII. Irrelevant vertices in linkage problems
- The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
- Primal-dual approximation algorithms for integral flow and multicut in trees
- \(K_{6}\) minors in large 6-connected graphs
- A new proof of the flat wall theorem
- Graph minors. XX: Wagner's conjecture
- Graph minors. III. Planar tree-width
- Linearity of grid minors in treewidth with applications through bidimensionality
- Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
- Linear connectivity forces large complete bipartite minors
- Graph minors. XXI. graphs with unique linkages
- Graph minors. V. Excluding a planar graph
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Disjoint paths in graphs
- 2-linked graphs
- Highly connected sets and the excluded grid theorem
- Quickly excluding a planar graph
- Graph minors. XIII: The disjoint paths problem
- Tree-width and planar minors
- Solving the 2-disjoint paths problem in nearly linear time
- A shorter proof of the graph minor algorithm
- Excluded Grid Theorem
- Polynomial Bounds for the Grid-Minor Theorem
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Edge-Disjoint Paths in Planar Graphs with Constant Congestion
- Towards Tight(er) Bounds for the Excluded Grid Theorem
- Bidimensional Parameters and Local Treewidth
- Directed Nowhere Dense Classes of Graphs
- A simpler algorithm and shorter proof for the graph minor decomposition
