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
Abstract:
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)