Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
type: Item
instance of: scholarly article
title: Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
zbMATH Open document ID: 1184.05121
author: Erik D. Demaine
author: Mohammad T. Hajiaghayi
author: Ken-ichi Kawarabayashi
published in: Algorithmica
publication date: 2009-06-22T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C83
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5566995
zbMATH Keywords: graph minors
zbMATH Keywords: graph algorithms
zbMATH Keywords: grid graphs
zbMATH Keywords: treewidth
zbMATH Keywords: bidimensionality
zbMATH Keywords: Wagner's conjecture
MaRDI profile type: Publication
full work available at URL: s00453-007-9138-y
OpenAlex ID: W1551708885
cites work: Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
cites work: Parameterized complexity: exponential speed-up for planar graph problems
cites work: \(K_{a,k}\) minors in graphs of bounded tree-width
cites work: Linear connectivity forces large complete bipartite minors
cites work: Treewidth of planar graphs: connections with duality
cites work: Q4448744
cites work: Vertex cover: Further observations and further improvements
cites work: Approximation algorithms for independent sets in map graphs
cites work: Map graphs
cites work: Q5501346
cites work: Graph Drawing
cites work: Bidimensionality: new connections between FPT algorithms and PTASs
cites work: Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality
cites work: Quickly deciding minor-closed parameters in general graphs
cites work: Q4411278
cites work: Bidimensional Parameters and Local Treewidth
cites work: Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
cites work: Q4449223
cites work: Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
cites work: The Bidimensional Theory of Bounded-Genus Graphs
cites work: Q4947393
cites work: Highly connected sets and the excluded grid theorem
cites work: Connectivity, graph minors, and subgraph multiplicity
cites work: Diameter and treewidth in minor-closed graph families
cites work: Nonconstructive tools for proving polynomial-time decidability
cites work: Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
cites work: Kernels in planar digraphs
cites work: Ordering by Divisibility in Abstract Algebras
cites work: The NP-completeness column: An ongoing guide
cites work: Q4708588
cites work: Q4414505
cites work: Q4218137
cites work: Q5501358
cites work: On graph powers for leaf-labeled trees
cites work: Q4352948
cites work: Undirected ST-connectivity in log-space
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: Graph minors. V. Excluding a planar graph
cites work: Graph minors. IX: Disjoint crossed paths
cites work: Graph minors. X: Obstructions to tree-decomposition
cites work: Q4273877
cites work: Graph minors. XI: Circuits on a surface
cites work: Graph minors. XII: Distance on a surface
cites work: Graph minors. XX: Wagner's conjecture
cites work: Quickly excluding a planar graph
cites work: Call routing and the ratcatcher
cites work: Excluding minors in nonplanar graphs of girth at least five
DOI: 10.1007/S00453-007-9138-Y
description: scientific article; zbMATH DE number 5566995