Grid minors in damaged grids

MaRDI QIDQ405308zbMATH OpenFDO

Authors David Eppstein

Publication date 4 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.1136, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p20

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

treewidthgraph minorsgrid graphsvertex deletionshallow minorssubgraphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph minors (05C83)

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

• Polynomial bounds for the grid-minor theorem
• Tree-width and large grid minors in planar graphs
• Grid minors of graphs on the torus
• Polynomial bounds for the grid-minor theorem
• Linearity of grid minors in treewidth with applications through bidimensionality

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

(4)

• Combinational numerical methods with minimum discretization error
• Approximation algorithms for Euler genus and related problems
• Characterising graphs with no subdivision of a wheel of bounded diameter
• Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets

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)