Graph minors. III. Planar tree-width

1984/02/01 by Neil Robertson, Paul Seymour, P.D Seymour · 21 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Book embedding #Butterfly graph #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Discrete mathematics #Graph #Graph minor #Line graph #Mathematics #Outerplanar graph #Planar graph #Planar straight-line graph #Voltage graph

paper · doi:10.1016/0095-8956(84)90013-3

crossref issued 1984/02/01 · crossref published 1984/02/01 · crossref published-print 1984/02/01 · openalex publication_date 1984/02/01 · crossref created 2004/12/21 · crossref deposited 2019/01/30 · openalex created_date 2025/10/10 · crossref indexed 2026/07/02 · openalex updated_date 2026/07/23

Cited by

• Deciding first-order properties of locally tree-decomposable structures
• An Improvement of Reed’s Treewidth Approximation
• Large Induced Subgraphs via Triangulations and CMSO
• The pagenumber of k-trees is O(k)
• Pathwidth of outerplanar graphs
• Pathwidth of Planar and Line Graphs
• Directed Tree-Width
• On the Path-Width of Planar Graphs
• On self duality of pathwidth in polyhedral graph embeddings
• Inapproximability of Treewidth and Related Problems
• Clifford Algebras Meet Tree Decompositions
• Local Tree-Width, Excluded Minors, and Approximation Algorithms
• 1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor
• Graph minors. I. Excluding a forest
• Graph minor theory
• A partial k-arboretum of graphs with bounded treewidth
• Kernelization: Theory of Parameterized Preprocessing
• Graph Polynomials and Their Applications I: The Tutte Polynomial
• Computing the Girth of a Planar Graph in Linear Time
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Tree decomposition [wikipedia]
• Treewidth [wikipedia]