Quickly excluding a planar graph

Neil Robertson, Paul Seymour, Robin Thomas

Research output: Contribution to journalArticle

275 Scopus citations

Abstract

In an earlier paper, the first two authors proved that for any planar graph H, every graph with no minor isomorphic to H has bounded tree width; but the bound given there was enormous. Here we prove a much better bound. We also improve the best known bound on the tree-width of planar graphs with no minor isomorphic to a g × g grid.

Original languageEnglish (US)
Pages (from-to)323-348
Number of pages26
JournalJournal of Combinatorial Theory, Series B
Volume62
Issue number2
DOIs
StatePublished - Nov 1994
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 'Quickly excluding a planar graph'. Together they form a unique fingerprint.

  • Cite this