Using Cellular Graph Embeddings in Solving All Pairs Shortest Paths Problems (Preliminary Version)

An algorithm for generating a succinct encoding of all-pairs shortest path information in an n-vertex directed planar G with O(n) edges is presented. The edges have real-valued costs, but the graph contains no negative cycles. The time complexity is given in terms of a topological embedding measure defined in the paper. The algorithm uses a decomposition of the graph into outerplanar subgraphs satisfying certain separator properties, and a linear-time algorithm is presented to find this decomposition. >

Authors

• Greg N. Frederickson

Keywords

• Encoding
• Routing
• Computer science
• Time measurement
• Costs
• Particle separators
• Shortest path problem
• Transmission line matrix methods
• Contracts
• Magnetic resonance
• Shortest Path
• Triangular
• Time Constant
• Undirected
• Directed Graph
• Subintervals
• Non-planar
• Vertex Degree
• Graph Properties
• Negative Cycle
• Topological Measures
• Sabbatical
• Planar Graphs
• Face Pairs
• Induced Subgraph
• Closed Surface
• Face-based
• Edge Labels
• Euler Characteristic
• Sequence Of Vertices
• Partial Decomposition