Graph minors. I. Excluding a forest

1983/08/01 by Neil Robertson, Paul Seymour, P.D. Seymour · 35 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Graph #Interconnection Networks and Systems #Line graph #Mathematics #Minor (academic) #Pairwise comparison #Path (computing) #Robertson–Seymour theorem #Statistics

paper · doi:10.1016/0095-8956(83)90079-5

crossref issued 1983/08/01 · crossref published 1983/08/01 · crossref published-print 1983/08/01 · openalex publication_date 1983/08/01 · crossref created 2006/04/05 · crossref deposited 2019/01/17 · openalex created_date 2025/10/10 · crossref indexed 2026/06/10 · openalex updated_date 2026/08/03

Citations

• Graph minors. III. Planar tree-width

Cited by

• Narrowness, pathwidth, and their application in natural language processing
• Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
• Grad and classes with bounded expansion II. Algorithmic aspects
• All Structured Programs Have Small Tree Width and Good Register Allocation
• On the pathwidth of chordal graphs
• Tree-width, path-width, and cutwidth
• Pathwidth of outerplanar graphs
• Approximation of pathwidth of outerplanar graphs
• Graph minor hierarchies
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Tree-width and path-width of comparability graphs of interval orders
• Crossing-number critical graphs have bounded path-width
• Memory Requirements for Table Computations in Partial \sl k -Tree Algorithms
• A simple linear-time algorithm for finding path-decompositions of small width
• A Distributed Algorithm for Computing the Node Search Number in Trees
• On the Path-Width of Planar Graphs
• Quickly excluding a forest
• Computing Optimal Linear Layouts of Trees in Linear Time
• Pathwidth of Circular-Arc Graphs
• The pathwidth and treewidth of cographs
• On search decision and the efficiency of polynomial-time algorithms
• Obstruction set isolation for the gate matrix layout problem
• Line graphs of bounded clique-width
• Graph Minors I: A Short Proof of the Path-width Theorem
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• Graph minors. V. Excluding a planar graph
• Chapter 8 Algorithmic implications of the graph minor theorem
• A partial k-arboretum of graphs with bounded treewidth
• Computing directed path-width and directed tree-width of recursively defined digraphs
• Graph Polynomials and Their Applications I: The Tutte Polynomial
• Excluding infinite minors
• Sur un nouvel invariant des graphes et un critère de planarité
• Graph minor [wikipedia]
• Pathwidth [wikipedia]
• Robertson–Seymour theorem [wikipedia]