Given a graph G and two pairs of vertices s1, t1 and s2, t2, the two disjoint paths problem asks for vertex-disjoint paths connecting si with ti, 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 K3,3 or K5) is given. This complements the known NC planarity algorithms, which give a planar embedding in the positive case; the algorithm here 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.