OPTIMAL PARALLEL ALGORITHMS FOR PATH PROBLEMS ON PLANAR GRAPHS

Given a biconnected planar graph G and a pair of vertices s and t, the two disjoint problem asks to find a pair of internally disjoint paths from s to t. We present a simple and efficient parallel algorithm for the same. Our algorithm uses the notion of bridges in a novel way and this results in a more elegant and simple algorithm than the existing one. The all-bidirectional-edges (ABE) problem is to find an edge lab eling such that an edge (u, v) in E is labeled [u, v] or [v, u] or bot h depending on the existence of a simple path from s to t that visits the vertices in the order u, v or v, u or both, respectively. We prese nt an optimal parallel algorithm for the same.