The authors give a parallel algorithm for finding vertex disjoint $s_1 ,t_1 $ and $s_2 ,t_2 $ paths in an undirected graph G. An important step in solving the general problem is solving the planar case. A new structural property yields the parallelization, as well as a simpler linear-time sequential algorithm for this case. The algorithm is extended to the nonplanar case by giving a parallel algorithm for finding a Kuratowski homeomorph, and, in particular, a homeomorph of $K_{3,3} $, in a nonplanar graph. The algorithms are processor efficient; in each case, the processor-time product of the algorithms is within a polylogarithmic factor of the best-known sequential algorithm.

Given a graph G and two pairs of vertices s/sub 1/, t/sub 1/ and s/sub 2/, t/sub 2/, the two disjoint paths problem asks for vertex-disjoint paths connecting s/sub i/ with t/sub i/, i=1, 2. A fast parallel (NC) algorithm is given for this problem, which has applications in certain routing situations. If G is nonplanar, an algorithm that finds a Kuratowski homeomorph in G (i.e. a subgraph homeomorphic to K/sub 3.3/ or K/sub 5/) is given. This complements the known NC planarity algorithms, which give a planar embedding in the positive case; the algorithm provides a certificate of nonplanarity in the negative case. Both algorithms are processor efficient; in each case, the processor-time product is within a polylogarithmic factor of the best known sequential algorithm.>