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

In the previous lecture, we saw how to recursively separate a planar graph into small pieces with small total boundary. In this lecture, we see how to obtain a so-called r-division, where each individual piece is guaranteed to have small boundary (as opposed to small total boundary as in the previous lecture). We also discuss how to quickly compute such an r-division. Using an algorithm for fast r-division, we obtain a simple SSSP algorithm for planar graphs that's faster than Dijkstra's algorithm.

We then discuss an even faster algorithm for SSSP in planar graphs. Despite the algorithm being quite simple, somewhat surprisingly, a rather involved analysis proves that its running time is linear, which is asymptotically optimal! We analyze a simplified version running in time O(n log logn). The algorithm works a little bit like Dijkstra's algorithm with “limited attention span”: The simple version starts by decomposing the graph into pieces of size O(log⁴ n). Then, it repeatedly works on the piece with the current minimum for log n steps until the shortest-path distance to all nodes has been found. We (partially) analyze the running time of the simplified algorithm.