Miao Guo, Yong Tao Pei, et al.
WCITS 2011
Given an undirected graph G = (V, E) and vertices s,,tt; s2,t2, the problem is to determine whether or not G admits two vertex disjoint paths P, and P2 connecting s, with t, and s2 with t2, respectively. This problem is solved by an O(n.m) algorithm (n = IVJ, m = JElL An important by-product of the paper is a theorem stating that if G is 4-connected and nonplanar, then such paths P, and P2 exist for any choice of s,, s2, h, and t2 (as conjectured by Watkins). © 1980, ACM. All rights reserved.
Miao Guo, Yong Tao Pei, et al.
WCITS 2011
Paula Harder, Venkatesh Ramesh, et al.
EGU 2023
Michael Factor, Dafna Sheinwald
Information Sciences
Ronald Fagin
Journal of the ACM