Polynomial Bounds for the Grid-Minor Theorem

DOI10.1145/2820609zbMath1410.05186OpenAlexW2563767922MaRDI QIDQ3177816

Julia Chuzhoy, Chandra Chekuri

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2820609

zbMATH Keywords

excluded grid theoremgraph minor theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Structural characterization of families of graphs (05C75) Graph minors (05C83) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (29)

Adapting the directed grid theorem into an \textsf{FPT} algorithm ⋮ Graph theory -- a survey on the occasion of the Abel Prize for László Lovász ⋮ Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs ⋮ Adapting the Directed Grid Theorem into an FPT Algorithm ⋮ Constant Congestion Brambles ⋮ Edge-treewidth: algorithmic and combinatorial properties ⋮ Approximating Pathwidth for Graphs of Small Treewidth ⋮ Grid induced minor theorem for graphs of small degree ⋮ A Tight Erdös--Pósa Function for Wheel Minors ⋮ The Parameterized Complexity of Motion Planning for Snake-Like Robots ⋮ Minor-Closed Graph Classes with Bounded Layered Pathwidth ⋮ Towards tight(er) bounds for the excluded grid theorem ⋮ Polynomial treedepth bounds in linear colorings ⋮ Deciding whether a grid is a topological subgraph of a planar graph is NP-complete ⋮ Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes ⋮ Unnamed Item ⋮ Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor ⋮ Fractal dimension and lower bounds for geometric problems ⋮ Unavoidable minors for graphs with large \(\ell_p\)-dimension ⋮ On tseitin formulas, read-once branching programs and treewidth ⋮ Extension complexity of the correlation polytope ⋮ Unnamed Item ⋮ Finding Detours is Fixed-Parameter Tractable ⋮ Bidimensionality and Kernels ⋮ Treewidth of graphs with balanced separations ⋮ Packing Cycles Faster Than Erdos--Posa ⋮ Contraction-Bidimensionality of Geometric Intersection Graphs ⋮ On the impact of treewidth in the computational complexity of freezing dynamics ⋮ New limits of treewidth-based tractability in optimization

This page was built for publication: Polynomial Bounds for the Grid-Minor Theorem