Graph minors. V. Excluding a planar graph

1986/08/01 by Neil Robertson, Paul Seymour, P.D Seymour · 500 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Butterfly graph #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Graph minor #Graph power #Line graph #Mathematics #Outerplanar graph #Planar graph #Planar straight-line graph #Robertson–Seymour theorem #Voltage graph

paper · doi:10.1016/0095-8956(86)90030-4

published in Journal of Combinatorial Theory, Series B 41(1), 92-114 (Elsevier BV)

crossref issued 1986/08/01 · crossref published 1986/08/01 · crossref published-print 1986/08/01 · openalex publication_date 1986/08/01 · crossref created 2005/02/09 · crossref deposited 2019/01/29 · openalex created_date 2025/10/10 · crossref indexed 2026/07/24 · openalex updated_date 2026/08/03

Citations

• Graph minors. I. Excluding a forest

Cited by

• Bidimensional Parameters and Local Treewidth
• Deciding first-order properties of locally tree-decomposable structures
• Linearity of grid minors in treewidth with applications through bidimensionality
• Large Induced Subgraphs via Triangulations and CMSO
• Directed Tree-Width
• Graph minor hierarchies
• On search decision and the efficiency of polynomial-time algorithms
• Obstruction set isolation for the gate matrix layout problem
• An Erdős-Pósa theorem for cycles and faces of distinct lengths
• Oddomorphisms, Split-Off Minors, and the Strong Roberson Conjecture
• The price of homogeneity is polynomial
• Clique-width and induced topological minors
• Quickly excluding an annotated planar graph
• Chapter 8 Algorithmic implications of the graph minor theorem
• Diameter and Treewidth in Minor-Closed Graph Families
• Graph minor theory
• A partial k-arboretum of graphs with bounded treewidth
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Kernelization: Theory of Parameterized Preprocessing
• Descriptive and Parameterized Complexity
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• A directed flat wall theorem excluding a crossrow grid
• Linkless and flat embeddings in 3-space and the unknot problem
• Upper bounds to the clique width of graphs
• Excluding infinite minors
• Nonrepetitive colorings of graphs
• Nonrepetitive colorings of graphs of bounded tree-width
• Obstructions for partitioning into forests and outerplanar graphs
• Minor-Closed Graph Classes with Bounded Layered Pathwidth
• Computing crossing numbers in quadratic time
• On graphs with a simple structure of maximal cliques
• The Tractability of CSP Classes Defined by Forbidden Patterns
• A Tight Erdös--Pósa Function for Wheel Minors
• Hitting and Harvesting Pumpkins
• Rankings of Graphs
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Graph minors. X. Obstructions to tree-decomposition
• Approximating clique-width and branch-width
• Excluding a planar graph from GF ( q ) -representable matroids
• Monadic second-order logic and hypergraph orientation
• Color-coding
• Rank-width and vertex-minors
• Clique-sums, tree-decompositions and compactness
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. IV. Tree-width and well-quasi-ordering
• Graph minors. VIII. A kuratowski theorem for general surfaces
• Some Recent Progress and Applications in Graph Minor Theory
• Erdős–Pósa theorem [wikipedia]
• Graph minor [wikipedia]
• Graph structure theorem [wikipedia]
• Treewidth [wikipedia]