Graph minors. XVI. Excluding a non-planar graph

Neil Robertson; P. D. Seymour

doi:10.1016/S0095-8956(03)00042-X

Graph minors. XVI. Excluding a non-planar graph

Neil Robertson
, P. D. Seymour

Mathematics

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

282 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 language	English (US)
Pages (from-to)	43-76
Number of pages	34
Journal	Journal of Combinatorial Theory. Series B
Volume	89
Issue number	1
DOIs	https://doi.org/10.1016/S0095-8956(03)00042-X
State	Published - Sep 2003

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/S0095-8956(03)00042-X

Cite this

@article{7ed38fd5375c428fb6345cef0d591db1,

title = "Graph minors. XVI. Excluding a non-planar graph",

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

author = "Neil Robertson and Seymour, \{P. D.\}",

year = "2003",

month = sep,

doi = "10.1016/S0095-8956(03)00042-X",

language = "English (US)",

volume = "89",

pages = "43--76",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Graph minors. XVI. Excluding a non-planar graph

AU - Robertson, Neil

AU - Seymour, P. D.

PY - 2003/9

Y1 - 2003/9

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

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

UR - https://www.scopus.com/pages/publications/0141538200

UR - https://www.scopus.com/pages/publications/0141538200#tab=citedBy

U2 - 10.1016/S0095-8956(03)00042-X

DO - 10.1016/S0095-8956(03)00042-X

M3 - Article

AN - SCOPUS:0141538200

SN - 0095-8956

VL - 89

SP - 43

EP - 76

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 1

ER -

Graph minors. XVI. Excluding a non-planar graph

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this