CS 789 THEORY SEMINAR [home]

Speaker:    Philip Klein
Affiliation:  Brown University
Date:          April 26, 2004
Title:          Multiple-source shortest paths in planar graphs in O(n log n) time

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.