6.889: Algorithms for Planar Graphs and Beyond (Fall 2011)

We discuss data structures that answer node-to-node shortest-path and distance queries in planar graphs. Such data structures are also known as distance oracles. These oracles consist of two algorithms: (1) given a graph G, a preprocessing algorithm constructs a data structure and (2) given the data structure and a pair of nodes (v,w), a query algorithm computes and outputs the distance d(v,w) with respect to G. Three quantities and their tradeoffs are of particular interest: the running times of the preprocessing and query algorithms, and the space requirement of the data structure. We shall see that, for any planar graph and for any integer 1<r<n, there is a distance oracle with preprocessing time and space O(n²/r) and query time O(√r) (up to logarithmic factors).

To obtain these data structures, we shall use r-divisions, MSSP, and an efficient implementation of Dijkstra's algorithm, which we refer to as FR-Dijkstra (due to Fakcharoenphol and Rao). FR-Dijkstra is executed on a rather dense graph with the nodes being the boundary nodes of some pieces of an r-division and the edges representing the shortest paths within these pieces (so-called dense distance graphs). This particular implementation requires time (almost) proportional to the number of nodes only (as opposed to the number of edges, which is much bigger). The edges not considered are redundant and they can be safely ignored due to the Monge property, which essentially says that some shortest paths in planar graphs do not cross.

The efficient implementation of Dijkstra's algorithm and variants thereof also play a crucial role in subsequent lectures on shortest paths with negative lengths and maximum flow.