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 4 Video     [previous] [next]

[+] Single-source shortest paths: Nonnegative lengths in planar graphs.

We see how to improve upon Dijkstra's algorithm for the SSSP problem in planar graphs with non-negative edge lengths. As an important technique, we revisit the concept of an r-division.

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(log4 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.

Download Video: 360p, 720p

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

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