Algorithms for Planar Graphs (Fall 2013)

Shay Mozes

Lecture 7 Video [previous] [next]

[+] Shortest Paths in Dense Distance Graphs

This lecture begins with a brief discussion of the incision technique, and of r-divisions. The main topic of this lecture is an implementation of Dijkstra's algorithm on dense distance graphs, due to Fakcharoenphol and Rao. The running time is nearly linear in the number of vertices of the DDG, rather than in the number of edges as in a naive implementation of Dijkstra's algorithm.

Download Video: 720p

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