Efficient Parallel Algorithms for Planar st‐Graphs

Planar st ‐graphs find applications in a number of areas. In this paper we present efficient parallel algorithms for solving several fundamental problems on planar st ‐graphs. The problems we consider include all‐pairs shortest paths in weighted planar st ‐graphs, single‐source shortest paths in weighted planar layered digraphs (which can be reduced to single‐source shortest paths in certain special planar st ‐graphs), and depth‐first search in planar st ‐graphs. Our parallel shortest path techniques exploit the specific geometric and graphic structures of planar st ‐graphs, and involve schemes for partitioning planar st ‐graphs into subgraphs in a way that ensures that the resulting path length matrices have a monotonicity property [1], [2]. The parallel algorithms we obtain are a considerable improvement over the previously best known solutions (when they are applied to these st ‐graph problems), and are in fact relatively simple. The parallel computational models we use are the CREW PRAM and EREW PRAM.