Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction

DOI10.1007/s00453-007-9138-yzbMath1184.05121OpenAlexW1551708885MaRDI QIDQ1022348

Mohammad Taghi Hajiaghayi, Erik D. Demaine, Ken-ichi Kawarabayashi

Publication date: 22 June 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9138-y

zbMATH Keywords

treewidthgraph algorithmsgrid graphsgraph minorsbidimensionalityWagner's conjecture

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Neighborhood contraction in graphs, Graph Minors and Parameterized Algorithm Design, Grid minors in damaged grids, Connected search for a lazy robber, Low Polynomial Exclusion of Planar Graph Patterns, Contracting planar graphs to contractions of triangulations, Towards tight(er) bounds for the excluded grid theorem, Polynomial treewidth forces a large grid-like-minor, Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor, Complexity of the Steiner Network Problem with Respect to the Number of Terminals, Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness, Unnamed Item, Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. XX: Wagner's conjecture
• Quickly deciding minor-closed parameters in general graphs
• Linear connectivity forces large complete bipartite minors
• Graph minors. V. Excluding a planar graph
• Graph minors. X: Obstructions to tree-decomposition
• Highly connected sets and the excluded grid theorem
• Graph minors. XI: Circuits on a surface
• Call routing and the ratcatcher
• Quickly excluding a planar graph
• Diameter and treewidth in minor-closed graph families
• Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
• Graph minors. IX: Disjoint crossed paths
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• \(K_{a,k}\) minors in graphs of bounded tree-width
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• Graph minors. XII: Distance on a surface
• Kernels in planar digraphs
• Excluding Minors in Nonplanar Graphs of Girth at Least Five
• Approximation Algorithms for Independent Sets in Map Graphs
• Vertex Cover: Further Observations and Further Improvements
• On Graph Powers for Leaf-Labeled Trees
• Map graphs
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Treewidth of planar graphs: connections with duality
• The Bidimensional Theory of Bounded-Genus Graphs
• Undirected ST-connectivity in log-space
• Graph minors. II. Algorithmic aspects of tree-width
• Nonconstructive tools for proving polynomial-time decidability
• Connectivity, graph minors, and subgraph multiplicity
• Parameterized complexity: exponential speed-up for planar graph problems
• Bidimensional Parameters and Local Treewidth
• Graph Drawing
• Ordering by Divisibility in Abstract Algebras
• The NP-completeness column: An ongoing guide