Shortest Path Problems in Planar Graphs (Preliminary Version)

Graph decomposition and data structures techniques are presented that make possible faster algorithms for shortest paths in planar graphs. Improved algorithms are presented for the single source problem, the all pairs problem, and the problem of finding a minimum cut in an undirected graph.

Authors

• Greg N. Frederickson

Keywords

• Shortest path problem
• Costs
• Particle separators
• Data structures
• Partitioning algorithms
• Iterative algorithms
• Character generation
• Shortest Path
• Planar Graphs
• Minimum Cut
• Size Of Region
• Shortest Distance
• Maximum Flow
• Single Algorithm
• Previous Algorithms
• Undirected Network
• Single Path
• Pair Of Vertices
• Depth-first
• Dijkstra’s Algorithm
• Negative Cycle
• Small Nodes
• Search Phase
• Normal Nodes
• Minimum Cycle
• N Log N
• Separate Planes
• Subset Of Vertices