Grid minors in damaged grids

zbMATH Open1300.05292arXiv1303.1136MaRDI QIDQ405308FDOQ405308

Authors: David Eppstein 

Publication date: 4 September 2014

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

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.

Full work available at URL: https://arxiv.org/abs/1303.1136

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

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

zbMATH Keywords

treewidthgraph minorsgrid graphsvertex deletionshallow minorssubgraphs

Mathematics Subject Classification ID

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

Cites Work

• Graph minors. X: Obstructions to tree-decomposition
• Title not available (Why is that?)
• A partial k-arboretum of graphs with bounded treewidth
• Highly connected sets and the excluded grid theorem
• Quickly excluding a planar graph
• Linear min-max relation between the treewidth of \(H\)-minor-free graphs and its largest grid
• Sparsity. Graphs, structures, and algorithms
• Polynomial bounds for the grid-minor theorem
• Polynomial treewidth forces a large grid-like-minor
• Graph minors. I. Excluding a forest
• Über die Maximalzahl fremder unendlicher Wege in Graphen
• Title not available (Why is that?)
• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• Linearity of grid minors in treewidth with applications through bidimensionality
• Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
• Combinatorial aspects of geometric graphs
• A short proof of Halin's grid theorem
• Reconfiguring Arrays with Faults Part I: Worst-Case Faults
• Efficient erasure correcting codes
• Approximation algorithms for Euler genus and related problems
• Bandwidth and pathwidth of three-dimensional grids
• Tree-width and large grid minors in planar graphs
• Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications
• The treewidth and pathwidth of hypercubes
• On the Hadwiger's conjecture for graph products
• Tree-width of graphs without a \(3\times 3\) grid minor

Cited In (4)

• 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)