Graph Minors. XI. Circuits on a Surface

Neil Robertson; P. D. Seymour

doi:10.1006/jctb.1994.1007

Graph Minors. XI. Circuits on a Surface

Neil Robertson, P. D. Seymour

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

56 Scopus citations

Abstract

Let Γ be a graph or hypergraph drawn on a connected surface which is not a sphere, in such a way that every non-null-homotopic curve meets the drawing at least θ times. We show that this defines a “tangle of order θ” in Γ, in the sense of earlier papers of this series. Also, there is a natural distance function defined by the drawing, and we show that for any point c of the surface, and any θ′ > θ, the set of points within distance θ′ of c is simply-connected.

Original language	English (US)
Pages (from-to)	72-106
Number of pages	35
Journal	Journal of Combinatorial Theory, Series B
Volume	60
Issue number	1
DOIs	https://doi.org/10.1006/jctb.1994.1007
State	Published - Jan 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.1007

Cite this

@article{64a993d29cd24073a97b2f59b78fcbfd,

title = "Graph Minors. XI. Circuits on a Surface",

abstract = "Let Γ be a graph or hypergraph drawn on a connected surface which is not a sphere, in such a way that every non-null-homotopic curve meets the drawing at least θ times. We show that this defines a “tangle of order θ” in Γ, in the sense of earlier papers of this series. Also, there is a natural distance function defined by the drawing, and we show that for any point c of the surface, and any θ′ > θ, the set of points within distance θ′ of c is simply-connected.",

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

year = "1994",

month = jan,

doi = "10.1006/jctb.1994.1007",

language = "English (US)",

volume = "60",

pages = "72--106",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Graph Minors. XI. Circuits on a Surface

AU - Robertson, Neil

AU - Seymour, P. D.

PY - 1994/1

Y1 - 1994/1

N2 - Let Γ be a graph or hypergraph drawn on a connected surface which is not a sphere, in such a way that every non-null-homotopic curve meets the drawing at least θ times. We show that this defines a “tangle of order θ” in Γ, in the sense of earlier papers of this series. Also, there is a natural distance function defined by the drawing, and we show that for any point c of the surface, and any θ′ > θ, the set of points within distance θ′ of c is simply-connected.

AB - Let Γ be a graph or hypergraph drawn on a connected surface which is not a sphere, in such a way that every non-null-homotopic curve meets the drawing at least θ times. We show that this defines a “tangle of order θ” in Γ, in the sense of earlier papers of this series. Also, there is a natural distance function defined by the drawing, and we show that for any point c of the surface, and any θ′ > θ, the set of points within distance θ′ of c is simply-connected.

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

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

U2 - 10.1006/jctb.1994.1007

DO - 10.1006/jctb.1994.1007

M3 - Article

AN - SCOPUS:38149143442

SN - 0095-8956

VL - 60

SP - 72

EP - 106

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 1

ER -

Graph Minors. XI. Circuits on a Surface

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this