Publication Details
Title: Planar Graph Decomposition and All Pairs Shortest Paths
Author: G. N. Frederickson
Group: ICSI Technical Reports
Date: March 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-015.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-89-015
Bibliographic Reference:
G. N. Frederickson. Planar Graph Decomposition and All Pairs Shortest Paths. ICSI Technical Report TR-89-015, March 1989
Author: G. N. Frederickson
Group: ICSI Technical Reports
Date: March 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-015.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-89-015
Bibliographic Reference:
G. N. Frederickson. Planar Graph Decomposition and All Pairs Shortest Paths. ICSI Technical Report TR-89-015, March 1989