Tech Report CS-93-35

A Linear-Processor Polylog-Time Algorithm for Shortest Paths in Planar Graphs

Philip N. Klein and Sairam Subramanian

September 1993


We give an algorithm requiring polylog time and a linear number of processors to solve single-source shortest paths in directed planar graphs, bounded-genus graphs, and two-dimensional overlap graphs. More generally, the algorithm works for any graph provided with a decomposition tree constructed using size-$O(\sqrt{n}\mbox{polylog } n)$ separators.

(complete text in pdf or gzipped postscript)