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.
Publication Year: 1988
Publication Date: 1988-10-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 160
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot