Planar graph decomposition and all pairs shortest paths
- 3 January 1991
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 38 (1) , 162-204
- https://doi.org/10.1145/102782.102788
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 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.Keywords
This publication has 17 references indexed in Scilit:
- Efficient Message Routing in Planar NetworksSIAM Journal on Computing, 1989
- Designing networks with compact routing tablesAlgorithmica, 1988
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- Deques with heap orderInformation Processing Letters, 1986
- Labelling and Implicit Routing in NetworksThe Computer Journal, 1985
- Implicit Data Structures for the Dictionary ProblemJournal of the ACM, 1983
- Implicit data structures for fast search and updateJournal of Computer and System Sciences, 1980
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithmsJournal of Computer and System Sciences, 1976
- Efficient Planarity TestingJournal of the ACM, 1974
- A Theorem on Boolean MatricesJournal of the ACM, 1962