Planar graphs, negative weight edges, shortest paths, and near linear time

In this paper, we present an O(nlog3n) time algorithm for finding shortest paths in an n-node planar graph with real weights. This can be compared to the best previous strongly polynomial time algorithm developed by Lipton, Rose, and Tarjan in 1978 which runs in O(n3/2) time, and the best polynomial time algorithm developed by Henzinger, Klein, Subramanian, and Rao in 1994 which runs in time. We also present significantly improved data structures for reporting distances between pairs of nodes and algorithms for updating the data structures when edge weights change.