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] [Accessibility]

Lecture 13 Video     [previous] [next]

[+]Approximate distance oracles for planar graphs.

We discuss data structures that answer approximate node-to-node shortest-path and distance queries in planar graphs. Such data structures are also known as approximate distance oracles. Analogously to exact distance oracles, approximate distance oracles consist of two algorithms: (1) given a graph G and an approximation parameter ε, 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 an estimate for the distance d(v,w) with respect to G. The estimate is supposed to be at most (1+ε) times larger than the actual shortest-path distance (and no smaller).

We shall see that, for any planar graph and for any ε>0, there is a (1+ε)-approximate distance oracle with preprocessing time O((n/ε) log2 n) and space O((n/ε) log n) and query time O((1/ε) log n).

To obtain these data structures, we recursively separate the graph by shortest paths. On these path separators, we carefully select a set of portals, through which we approximate shortest paths that intersect with the separator path.

Download Video: 360p, 720p

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

Lecture notes, page 1/7[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.