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

Erik Demaine, Shay Mozes, Christian Sommer, Siamak Tazari

[Home] [Problem Sets] [Project] [Lectures] [Problem Session Notes] [Klein's Book]

Lecture 12 Video     [previous] [next]

[+] Exact distance oracles for planar graphs.

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(n2/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.

Download Video: 360p, 720p

Lecture notes, page 1/9[previous page][next page][PDF]

Lecture notes, page 1/9[previous page][next page][PDF]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email Erik.