[+] Shortest paths and recursive divisions in minorfree graphs. 
We discuss recursive divisions and how to obtain
them in planar and minorfree graphs. This is one of the main tools
that is used to obtain a lineartime SSSP algorithm and, in fact, once
we have a suitable recursive division, the same SSSP algorithm works
for both planar and minorclosed classes. However, both the recursive
division algorithm and the SSSP analysis require the graph to be of
bounded degree and it turns out that, in general Hminorfree graphs,
a reduction to the boundeddegree case as in the planar case is not
possible. We will see how to use knitted Hpartitions to overcome
this issue and obtain a generalized recursive division algorithm for
all Hminorfree classes.
[HKRS97] M. R. Henzinger, P. N. Klein, S. Rao, S. Subramanian: Faster shortest path algorithms for planar graphs. In: Journal of Computer and System Sciences, vol. 55(1):pp. 323, 1997. 
Lecture notes, page 1/9 •
[previous page] •
[next page] •
[PDF]
Lecture notes, page 1/9 • [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.