[+] Contraction decomposition of boundedgenus and Hminorfree graphs: PTASs, FPT algortihms, kcut, radial coloring, tight roots, radially shortest paths, te structures 

This lecture is about contraction decomposition: partitioning the edges of the graph into k pieces (for a specified integer k ≥ 2) such that contracting any piece reduces the graph down to bounded treewidth. We've already seen in Lecture 15 how to do this for planar graphs. In this lecture, we see how to do it in boundedgenus graphs in detail, and Hminorfree graphs at a high level. We also briefly discuss applications of contraction decomposition to PTASs and FPT algorithms. The Hminorfree contraction decomposition is a new result from STOC 2011 by Demaine, Hajiaghayi, and Kawarabayashi. 
Lecture notes, page 1/7 •
[previous page] •
[next page] •
[PDF]
Lecture notes, page 1/7 • [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.