Planar Graph Decomposition and All Pairs Shortest Paths

TitlePlanar Graph Decomposition and All Pairs Shortest Paths
Publication TypeTechnical Report
Year of Publication1989
AuthorsFrederickson, G. N.
Other Numbers514
Abstract

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 not 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 outerplanar graph. * Has since been revised by author. Contact him via "gnf at cs.purdue.edu" for a current copy.

URLhttp://www.icsi.berkeley.edu/pubs/techreports/tr-89-015.pdf
Bibliographic Notes

ICSI Technical Report TR-89-015

Abbreviated Authors

G. N. Frederickson

ICSI Publication Type

Technical Report