Local Tree-Width, Excluded Minors, and Approximation Algorithms

2003/12/01 by Martin Grohe · 16 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bounded function #Chordal graph #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Dominating set #Graph #Graph Labeling and Dimension Problems #Independent set #Mathematics #Maximal independent set #Tree (set theory) #Vertex (graph theory) #Vertex cover

paper · doi:10.1007/s00493-003-0037-9

crossref issued 2003/12/01 · crossref published 2003/12/01 · crossref published-print 2003/12/01 · openalex publication_date 2003/12/01 · crossref created 2004/05/12 · crossref deposited 2019/05/28 · openalex created_date 2025/10/10 · crossref indexed 2026/03/26 · openalex updated_date 2026/07/29

Citations

• Applications of a Planar Separator Theorem
• Graph minors. III. Planar tree-width
• Approximation algorithms for NP-complete problems on planar graphs

Cited by

• Bidimensional Parameters and Local Treewidth
• Deciding first-order properties of locally tree-decomposable structures
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Linearity of grid minors in treewidth with applications through bidimensionality
• Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring
• Improved approximation algorithms for minimum-weight vertex separators
• An Erdős-Pósa theorem for cycles and faces of distinct lengths
• The price of homogeneity is polynomial
• Quickly excluding an annotated planar graph
• Sample compression schemes for balls in structurally sparse graphs
• A linear-time algorithm to find a separator in a graph excluding a minor
• Diameter and Treewidth in Minor-Closed Graph Families, Revisited
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Algorithms for Graphs Embeddable with Few Crossings per Edge
• Minor-Closed Graph Classes with Bounded Layered Pathwidth
• Graph minor [wikipedia]
• Independent set (graph theory) [wikipedia]