Graph minors. XVI. Excluding a non-planar graph

Neil Robertson, P. D. Seymour

Research output: Contribution to journalArticlepeer-review

251 Scopus citations

Abstract

This paper contains the cornerstone theorem of the series. We study the structure of graphs with no minor isomorphic to a fixed graph L, when L is non-planar. (The case when L is planar was studied in an earlier paper.) We find that every graph with no minor isomorphic to L may be constructed by piecing together in a tree-structure graphs each of which "almost" embeds in some surface in which L cannot be embedded.

Original languageEnglish (US)
Pages (from-to)43-76
Number of pages34
JournalJournal of Combinatorial Theory. Series B
Volume89
Issue number1
DOIs
StatePublished - Sep 2003

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Graph minors. XVI. Excluding a non-planar graph'. Together they form a unique fingerprint.

Cite this