Efficient parallel algorithms are presented, on the CREW PRAM model, for generating a succinct encoding of all pairs shortest path information in a directed planar graph G with real-valued edge costs but no negative cycles. The authors assume that a planar embedding of G is given, together with a set of q faces that cover all the vertices. Then the present algorithm runs in O(log2n) time and employs O(nq+M(q)) processors (where M(t) is the number of processors required to multiply two t×t matrices in O(logt) time). It should be noted here that whenever q<n then the processor bound is better than the best previous one (M(n)). O(log2n) time, n-processor algorithms are presented for various subproblems, including that of generating all pairs shortest path information in a directed outerplanar graph. The present work is based on the fundamental hammock-decomposition technique of G. Frederickson. The authors achieve this decomposition in O(lognlog*n) parallel time by using O(n) processors. The hammock-decomposition seems to be a fundamental operation that may help in improving efficiency of many parallel (and sequential) graph algorithms.
