Quickly excluding a planar graph

Neil Robertson; Paul Seymour; Robin Thomas

doi:10.1006/jctb.1994.1073

Quickly excluding a planar graph

Neil Robertson, Paul Seymour, Robin Thomas

Research output: Contribution to journal › Article › peer-review

310 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 language	English (US)
Pages (from-to)	323-348
Number of pages	26
Journal	Journal of Combinatorial Theory, Series B
Volume	62
Issue number	2
DOIs	https://doi.org/10.1006/jctb.1994.1073
State	Published - Nov 1994
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1006/jctb.1994.1073

Cite this

@article{46b8821f6adc470b8d88b8791be59062,

title = "Quickly excluding a planar graph",

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.",

author = "Neil Robertson and Paul Seymour and Robin Thomas",

year = "1994",

month = nov,

doi = "10.1006/jctb.1994.1073",

language = "English (US)",

volume = "62",

pages = "323--348",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Quickly excluding a planar graph

AU - Robertson, Neil

AU - Seymour, Paul

AU - Thomas, Robin

PY - 1994/11

Y1 - 1994/11

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0004455288&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0004455288&partnerID=8YFLogxK

U2 - 10.1006/jctb.1994.1073

DO - 10.1006/jctb.1994.1073

M3 - Article

AN - SCOPUS:0004455288

SN - 0095-8956

VL - 62

SP - 323

EP - 348

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 2

ER -

Quickly excluding a planar graph

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this