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

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/ε) log² 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.