Graph minors. VII. Disjoint paths on a surface

Neil Robertson; P. D. Seymour

doi:10.1016/0095-8956(88)90070-6

Graph minors. VII. Disjoint paths on a surface

Neil Robertson, P. D. Seymour

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

134 Scopus citations

Abstract

Let s₁, t₁, s₂, t₂, ..., s_k, t_k be vertices of a graph G drawn in a surface Σ. When are there k vertex-disjoint paths of G linking s_i and t_i (1 ≤ i ≤ k)? We study sufficient conditions-for instance, it suffices that G is connected and "uses up" the surface adequately, and all the s_i's and t_j's are mutually "far apart." Our results are applied to yield a polynomially bounded algorithm to solve the problem for fixed Σ and k.

Original language	English (US)
Pages (from-to)	212-254
Number of pages	43
Journal	Journal of Combinatorial Theory, Series B
Volume	45
Issue number	2
DOIs	https://doi.org/10.1016/0095-8956(88)90070-6
State	Published - Oct 1988
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(88)90070-6

Cite this

@article{7ec3386fea4f49769478623e741218aa,

title = "Graph minors. VII. Disjoint paths on a surface",

abstract = "Let s1, t1, s2, t2, ..., sk, tk be vertices of a graph G drawn in a surface Σ. When are there k vertex-disjoint paths of G linking si and ti (1 ≤ i ≤ k)? We study sufficient conditions-for instance, it suffices that G is connected and {"}uses up{"} the surface adequately, and all the si's and tj's are mutually {"}far apart.{"} Our results are applied to yield a polynomially bounded algorithm to solve the problem for fixed Σ and k.",

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

year = "1988",

month = oct,

doi = "10.1016/0095-8956(88)90070-6",

language = "English (US)",

volume = "45",

pages = "212--254",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Graph minors. VII. Disjoint paths on a surface

AU - Robertson, Neil

AU - Seymour, P. D.

PY - 1988/10

Y1 - 1988/10

N2 - Let s1, t1, s2, t2, ..., sk, tk be vertices of a graph G drawn in a surface Σ. When are there k vertex-disjoint paths of G linking si and ti (1 ≤ i ≤ k)? We study sufficient conditions-for instance, it suffices that G is connected and "uses up" the surface adequately, and all the si's and tj's are mutually "far apart." Our results are applied to yield a polynomially bounded algorithm to solve the problem for fixed Σ and k.

AB - Let s1, t1, s2, t2, ..., sk, tk be vertices of a graph G drawn in a surface Σ. When are there k vertex-disjoint paths of G linking si and ti (1 ≤ i ≤ k)? We study sufficient conditions-for instance, it suffices that G is connected and "uses up" the surface adequately, and all the si's and tj's are mutually "far apart." Our results are applied to yield a polynomially bounded algorithm to solve the problem for fixed Σ and k.

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

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

U2 - 10.1016/0095-8956(88)90070-6

DO - 10.1016/0095-8956(88)90070-6

M3 - Article

AN - SCOPUS:45449125778

SN - 0095-8956

VL - 45

SP - 212

EP - 254

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 2

ER -

Graph minors. VII. Disjoint paths on a surface

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this