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 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 | |
State | Published - Oct 1988 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics