Multiple-source shortest paths in planar graphs in O(n log n) time
Philip Klein, Brown University
April 23, 2004

Abstract

We describe an algorithm for efficiently finding multiple-source, multiple-destination shortest-path distances in a planar graph. More precisely, given an n-node planar graph with nonnegative edge-lengths, the algorithm takes O(n log n) time to construct a data structure that supports queries of the following form in O(log n)time: given a destination node t on the boundary of the infinite face, and given a start node s anywhere, find the s-to-t distance.

The algorithm can also produce an O(n) structure that, for any node s and any node t on the boundary, finds the first edge on the shortest s-to-t path in O(log log degree(t)) time. Using this structure, one can for example obtain the shortest s-to-t path P in time O(|P|) if the graph has constant degree.

Using our algorithm, we obtain asymptotically faster algorithms for preprocessing to facilitate quick exact or approximate point-to-point distance queries in planar graphs (for arbitrary start and end nodes) and the corresponding shortest-path queries.