Algorithms for Planar Graphs and Beyond (2011)

In this lecture, we discuss linear-time algorithms for planar graphs that find a small (O(√n)) subset of the nodes whose removal partitions the graph into disjoint subgraphs of size at most 3n/4. 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. 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.

Source: courses.csail.mit.edu