A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs

Abstract

Given an n-vertex planar embedded digraph G with non-negative edge weights and a face f of G, Klein presented a data structure with O(n log n) space and preprocessing time which can answer any query (u, v) for the shortest path distance in G from u to v or from v to u in O(log n) time, provided u is on f. This data structure is a key tool in a number of state-of-the-art algorithms and data structures for planar graphs. Klein's data structure relies on dynamic trees and the persistence technique as well as a highly non-trivial interaction between primal shortest path trees and their duals. The construction of our data structure follows a completely different and in our opinion very simple divide-and-conquer approach that solely relies on Single-Source Shortest Path computations and contractions in the primal graph. Our space and preprocessing time bound is O(n log |f|) and query time is O(log |f|) which is an improvement over Klein's data structure when f has small size.