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

[+] Approximation schemes in planar graphs: Branchwidth and Baker's technique.
			In this lecture we introduce two additional graph decompositions - carving decomposition and branch decomposition. We prove a theorem of Tamaki that roughly says that the branch-width of a planar graph is at most twice its radius. We use the radius bound on the width of a decomposition of planar graphs to devise a PTAS for minimum vertex cover. This PTAS is an example of a general technique due to Baker, which can be applied to many other problems.

Download Video: 360p, 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 Erik.