Excluded grid theorem: improved and simplified
From MaRDI portal
Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph minors (05C83) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)
Recommendations
- Towards tight(er) bounds for the excluded grid theorem
- Towards tight(er) bounds for the excluded grid theorem
- Polynomial bounds for the grid-minor theorem
- Polynomial bounds for the grid-minor theorem
- Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
Cites work
- Approximate distance oracles
- Approximate distance oracles with constant query time
- Automata, Languages and Programming
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Fast C-K-R partitions of sparse graphs
- Near-Linear Time Construction of Sparse Neighborhood Covers
- On approximate distance labels and routing schemes with affine stretch
- On sparse spanners of weighted graphs
- Ramsey partitions and proximity data structures
- Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
- Shortest-path queries in static networks
Cited in
(28)- Highly connected sets and the excluded grid theorem
- Treewidth distance on phylogenetic trees
- Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs
- On Tseitin formulas, read-once branching programs and treewidth
- Bounded-depth Frege complexity of Tseitin formulas for all graphs
- Sparse obstructions for minor-covering parameters
- Towards tight(er) bounds for the excluded grid theorem
- Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
- Minors in graphs of large _r-girth
- Packing and covering immersion-expansions of planar sub-cubic graphs
- Grid induced minor theorem for graphs of small degree
- Hitting forbidden minors: approximation and kernelization
- Low polynomial exclusion of planar graph patterns
- Reduction rules for the maximum parsimony distance on phylogenetic trees
- Polynomial bounds for the grid-minor theorem
- Packing and covering immersion models of planar subcubic graphs
- Bidimensionality and kernels
- Constant congestion routing of symmetric demands in planar directed graphs
- A polynomial excluded-minor approximation of treedepth
- Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
- Minor-Closed Graph Classes with Bounded Layered Pathwidth
- Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
- Packing cycles faster than Erdős-Pósa
- Towards tight(er) bounds for the excluded grid theorem
- Polynomial bounds for the grid-minor theorem
- (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels
- Polynomial treewidth forces a large grid-like-minor
- A new proof of the flat wall theorem
This page was built for publication: Excluded grid theorem: improved and simplified
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941560)
