Graph minors. VI. Disjoint paths across a disc

Neil Robertson; P. D. Seymour

doi:10.1016/0095-8956(86)90031-6

Graph minors. VI. Disjoint paths across a disc

Neil Robertson, P. D. Seymour

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

55 Scopus citations

Abstract

Let G be a graph drawn on a disc, and let the vertices of G on the boundary of the disc be s₁, ..., s_k, t₁, ..., t_k in some order. When are there k vertex-disjoint paths of G joining s_i and t_i (1 ≤ i ≤ k), respectively? We give a structural characterization and a polynomial algorithm for this problem. We also solve the same question when the disc is replaced by a cylinder.

Original language	English (US)
Pages (from-to)	115-138
Number of pages	24
Journal	Journal of Combinatorial Theory, Series B
Volume	41
Issue number	1
DOIs	https://doi.org/10.1016/0095-8956(86)90031-6
State	Published - Aug 1986
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/0095-8956(86)90031-6

Cite this

@article{a035c852a1f645edab5abe22d7c5ccc6,

title = "Graph minors. VI. Disjoint paths across a disc",

abstract = "Let G be a graph drawn on a disc, and let the vertices of G on the boundary of the disc be s1, ..., sk, t1, ..., tk in some order. When are there k vertex-disjoint paths of G joining si and ti (1 ≤ i ≤ k), respectively? We give a structural characterization and a polynomial algorithm for this problem. We also solve the same question when the disc is replaced by a cylinder.",

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

year = "1986",

month = aug,

doi = "10.1016/0095-8956(86)90031-6",

language = "English (US)",

volume = "41",

pages = "115--138",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Graph minors. VI. Disjoint paths across a disc

AU - Robertson, Neil

AU - Seymour, P. D.

PY - 1986/8

Y1 - 1986/8

N2 - Let G be a graph drawn on a disc, and let the vertices of G on the boundary of the disc be s1, ..., sk, t1, ..., tk in some order. When are there k vertex-disjoint paths of G joining si and ti (1 ≤ i ≤ k), respectively? We give a structural characterization and a polynomial algorithm for this problem. We also solve the same question when the disc is replaced by a cylinder.

AB - Let G be a graph drawn on a disc, and let the vertices of G on the boundary of the disc be s1, ..., sk, t1, ..., tk in some order. When are there k vertex-disjoint paths of G joining si and ti (1 ≤ i ≤ k), respectively? We give a structural characterization and a polynomial algorithm for this problem. We also solve the same question when the disc is replaced by a cylinder.

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

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

U2 - 10.1016/0095-8956(86)90031-6

DO - 10.1016/0095-8956(86)90031-6

M3 - Article

AN - SCOPUS:38249038848

SN - 0095-8956

VL - 41

SP - 115

EP - 138

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 1

ER -

Graph minors. VI. Disjoint paths across a disc

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this