Graph minors. VII. Disjoint paths on a surface

Neil Robertson, P. D. Seymour

Research output: Contribution to journalArticlepeer-review

131 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)212-254
Number of pages43
JournalJournal of Combinatorial Theory, Series B
Volume45
Issue number2
DOIs
StatePublished - Oct 1988
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Graph minors. VII. Disjoint paths on a surface'. Together they form a unique fingerprint.

Cite this