USING CELLULAR GRAPH EMBEDDINGS IN SOLVING ALL PAIRS SHORTEST PATHS PROBLEMS

An algorithm for generating a succinct encoding of all pairs shortest path information in an n-vertex directed graph ($) over right arrow G with O(n) edges is presented. The edges have real-valued costs, but th e graph contains no negative cycles. The algorithm runs in O(gamma(G)n + (gamma(C))(2) log gamma(G)) time, where gamma(G) is a topological e mbedding measure that we define for the corresponding undirected graph G. The algorithm uses a decomposition of the graph into O(gamma(G)) o uterplanar subgraphs satisfying certain separator properties, and a li near-time algorithm for finding this decomposition is presented. An al ternative encoding of all pairs shortest path information, as well as a succinct encoding of shortest distance information, is also given. ( C) 1995 Academic Press, Inc.