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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics