New divide-and-conquer techniques for finding disjoint paths

The paper presents the first parallel algorithm that finds maximal vertex-disjoint paths (MVDP) between sources and sinks in an undirected planar graph using poly-logarithm time and a linear number of processors on the parallel random access machine (PRAM). It also reduces the MVDP problem to the depth-first search (DFS) problem for the first time. The reduction treats a graph as a tripartite graph formed by sources, sinks, and maximal connected components of intermediate vertices, and successively uses a novel divide-and-conquer technique based on cycle separators to decompose those maximal connected components into smaller components. Consequently it constructs a DNC MVDP algorithm for graphs whose maximal connected components of intermediate vertices are planar