Graph minors. V. Excluding a planar graph

Neil Robertson, P. D. Seymour

Research output: Contribution to journalArticlepeer-review

541 Scopus citations

Abstract

We prove that for every planar graph H there is a number w such that every graph with no minor isomorphic to H can be constructed from graphs with at most w vertices, by piecing them together in a tree structure. This has several consequences; for example, it implies that: (i) if A is a set of graphs such that no member is isomorphic to a minor of another, and some member of A is planar, then A is finite; (ii) for every fixed planar graph H there is a polynomial time algorithm to test if an arbitrary graph has a minor isomorphic to H; (iii) there is a generalization of a theorem of Erdös and Pósa (concerning the maximum number of disjoint circuits in a graph) to planar structures other than circuits.

Original languageEnglish (US)
Pages (from-to)92-114
Number of pages23
JournalJournal of Combinatorial Theory, Series B
Volume41
Issue number1
DOIs
StatePublished - Aug 1986
Externally publishedYes

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. V. Excluding a planar graph'. Together they form a unique fingerprint.

Cite this