Abstract: We prove upper and lower bounds on the size of the largest square grid graph that is a subgraph, minor, or shallow minor of a graph in the form of a larger square grid from which a specified number of vertices have been deleted. Our bounds are tight to within constant factors. We also provide less-tight bounds on analogous problems for higher-dimensional grids.
Recommendations
Cites work
- scientific article; zbMATH DE number 1003278 (Why is no real title available?)
- scientific article; zbMATH DE number 1057879 (Why is no real title available?)
- A partial k-arboretum of graphs with bounded treewidth
- A short proof of Halin's grid theorem
- Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
- Approximation algorithms for Euler genus and related problems
- Bandwidth and pathwidth of three-dimensional grids
- Combinatorial aspects of geometric graphs
- Efficient erasure correcting codes
- Graph minors. I. Excluding a forest
- Graph minors. X: Obstructions to tree-decomposition
- Highly connected sets and the excluded grid theorem
- Improved bounds on the planar branchwidth with respect to the largest grid minor size
- Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid
- Linearity of grid minors in treewidth with applications through bidimensionality
- On the Hadwiger's conjecture for graph products
- Polynomial bounds for the grid-minor theorem
- Polynomial treewidth forces a large grid-like-minor
- Quickly excluding a planar graph
- Reconfiguring Arrays with Faults Part I: Worst-Case Faults
- Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications
- Sparsity. Graphs, structures, and algorithms
- The treewidth and pathwidth of hypercubes
- Tree-width and large grid minors in planar graphs
- Tree-width of graphs without a \(3\times 3\) grid minor
- Über die Maximalzahl fremder unendlicher Wege in Graphen
Cited in
(5)- Grid minors and products
- Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets
- Approximation algorithms for Euler genus and related problems
- Combinational numerical methods with minimum discretization error
- Characterising graphs with no subdivision of a wheel of bounded diameter
This page was built for publication: Grid minors in damaged grids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405308)
