Planar graph shortest path algorithm gets simpler clear analysis
Simple analysis of an algorithm for multiple-source shortest paths in planar graphs
Data Structures and Algorithms
Summary
This paper looks at the problem of finding shortest paths in flat, planar graphs from multiple starting points along the graph's edges. An earlier method by Klein solved this with a relatively efficient algorithm, but its explanation was complicated and hard to follow. The authors provide a new, simpler explanation and proof to help people understand how the algorithm works and why it is correct. This clearer analysis can make it easier to use and build on this algorithm in other applications.
What this means in practice
- •For map software developers: Improve routing features by efficiently computing shortest routes from multiple starting points on planar maps.
- •For bioinformatics software engineers: Use clearer shortest-path computations in planar graph models that compare genetic sequences or protein structures.
Authors
Philip N. Klein
Abstract
This paper addresses the following problem: given a planar embedding graph, compute a representation of the shortest-path trees rooted at all the boundary nodes of the graph. Klein gave an $O(n \log n)$ algorithm for this problem; the algorithm subsequently became an essential ingredient in dozens of algorithms, addressing problems ranging from distance oracles to edit distance. However, the correctness and analysis in that original paper is complicated and messy and hard to understand. In this paper, we give a simple and clear analysis.