Linearity of grid minors in treewidth with applications through bidimensionality

2008/01/01 by Erik D. Demaine, MohammadTaghi Hajiaghayi, Mohammadtaghi Hajiaghayi · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bounded function #Chordal graph #Clique-sum #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Graph minor #Limits and Structures in Graph Theory #Line graph #Mathematics #Outerplanar graph #Partial k-tree #Pathwidth #Planar graph #Tree-depth #Treewidth #Voltage graph

paper · doi:10.1007/s00493-008-2140-4

crossref issued 2008/01/01 · crossref published 2008/01/01 · crossref published-print 2008/01/01 · openalex publication_date 2008/01/01 · crossref created 2008/04/28 · crossref published-online 2008/04/29 · crossref deposited 2019/05/29 · openalex created_date 2025/10/10 · crossref indexed 2026/03/24 · openalex updated_date 2026/06/16

Citations

• 1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor
• Maximum Clique Transversals
• Efficient Approximation for Triangulation of Minimum Treewidth
• Applications of a Planar Separator Theorem
• Deciding first-order properties of locally tree-decomposable structures
• Local Tree-Width, Excluded Minors, and Approximation Algorithms
• Diameter and Treewidth in Minor-Closed Graph Families, Revisited
• Bidimensional Parameters and Local Treewidth
• Graph Minors. XVI. Excluding a non-planar graph
• Graph minors. V. Excluding a planar graph
• Diameter and Treewidth in Minor-Closed Graph Families
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Approximation algorithms for NP-complete problems on planar graphs
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs

Cited by

• Treewidth [wikipedia]