Excluded Grid Theorem

DOI10.1145/2746539.2746551zbMath1321.05248OpenAlexW2012927698MaRDI QIDQ2941560

Julia Chuzhoy

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

excluded grid theoremgrid minor theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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

Reduction rules for the maximum parsimony distance on phylogenetic trees ⋮ Treewidth distance on phylogenetic trees ⋮ Packing and Covering Immersion Models of Planar Subcubic Graphs ⋮ Minors in graphs of large \(\theta_r\)-girth ⋮ Packing and covering immersion-expansions of planar sub-cubic graphs ⋮ Sparse obstructions for minor-covering parameters ⋮ Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs ⋮ (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels ⋮ Minor-Closed Graph Classes with Bounded Layered Pathwidth ⋮ Towards tight(er) bounds for the excluded grid theorem ⋮ Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes ⋮ Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor ⋮ On tseitin formulas, read-once branching programs and treewidth ⋮ Bidimensionality and Kernels ⋮ Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs ⋮ Packing Cycles Faster Than Erdos--Posa ⋮ Bounded-depth Frege complexity of Tseitin formulas for all graphs

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming