Linearity of grid minors in treewidth with applications through bidimensionality

DOI10.1007/s00493-008-2140-4zbMath1174.05115OpenAlexW1976463682WikidataQ29036384 ScholiaQ29036384MaRDI QIDQ949776

Erik D. Demaine, Mohammad Taghi Hajiaghayi

Publication date: 21 October 2008

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-008-2140-4

zbMATH Keywords

treewidth grid minors

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering, Compactors for parameterized counting problems, A Retrospective on (Meta) Kernelization, Contraction bidimensionality of geometric intersection graphs, Towards the Graph Minor Theorems for Directed Graphs, Map graphs having witnesses of large girth, Graph Minors and Parameterized Algorithm Design, Unnamed Item, Chasing a Fast Robber on Planar Graphs and Random Graphs, Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs, Beyond bidimensionality: parameterized subexponential algorithms on directed graphs, On the excluded minor structure theorem for graphs of large tree-width, Bivariate complexity analysis of \textsc{Almost Forest Deletion}, Improved bounds on the planar branchwidth with respect to the largest grid minor size, Parameterized algorithms and data reduction for the short secluded s‐t‐path problem, Grid minors in damaged grids, Practical algorithms for branch-decompositions of planar graphs, Computing connected-\(k\)-subgraph cover with connectivity requirement, Graphs of linear growth have bounded treewidth, The complexity of two graph orientation problems, Low Polynomial Exclusion of Planar Graph Patterns, Subexponential algorithms for partial cover problems, FPT approximation and subexponential algorithms for covering few or many edges, Unnamed Item, Unnamed Item, Local search: is brute-force avoidable?, Catalan structures and dynamic programming in \(H\)-minor-free graphs, Subexponential parameterized algorithms, Confronting intractability via parameters, Spanners in sparse graphs, Polynomial treewidth forces a large grid-like-minor, Approximating Unique Games Using Low Diameter Graph Decomposition, Explicit linear kernels for packing problems, Target set selection for conservative populations, On the parameterized complexity of the edge monitoring problem, The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs, Fast minor testing in planar graphs, Parameterized complexity of the spanning tree congestion problem, FPT algorithms for connected feedback vertex set, Unnamed Item, Contraction obstructions for treewidth, Unnamed Item, Optimality program in segment and string graphs, Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor, Extension complexity of the correlation polytope, Strengthening Erdös-Pósa property for minor-closed graph classes, Bidimensionality and Kernels, Decomposition of Map Graphs with Applications., Deleting vertices to graphs of bounded genus, Searching for a Visible, Lazy Fugitive, Subexponential parameterized algorithms for graphs of polynomial growth, Contraction-Bidimensionality of Geometric Intersection Graphs, Lossy Kernels for Hitting Subgraphs, Unnamed Item, Unnamed Item, Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable

Cites Work