Planar graph decomposition and all pairs shortest paths

An algorithm is presented 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 algorithm runs in O ( pn ) time, where n is the number of vertices in G , and p is the minimum cardinality of a subset of the faces that cover all vertices, taken over all planar embeddings of G . The algorithm is based on a decomposition of the graph into O ( pn ) outerplanar subgraphs satisfying certain separator properties. Linear-time algorithms are presented for various subproblems including that of finding an appropriate embedding of G and a corresponding face-on-vertex covering of cardinality O ( p ), and of generating all pairs shortest path information in a directed outerplannar graph.