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]

Lecture 9 Video     [previous] [next]

[+] Approximation schemes in minor-free graphs I: local treewidth and apex-minor-free graphs, extension to H-minor-free graphs, deletion decomposition

In this lecture we look at Baker's technique from another perspective which leads to the notion of deletion decomposition: partitioning a graph into k parts such that removing any part gives a graph of low treewidth (in k). This idea of a simplifying decomposition is one of the main themes of this course.

We will then see how to generalize this idea from planar graphs to apex-minor-free graphs. To this end, we introduce the notion of local treewidth, one of the major concepts in algorithmic graph structure theory. For the generalization to H-minor-free graphs we will have to look at the Robertson-Seymour decomposition of H-minor-free graphs into clique-sums of almost embeddable graphs.

All in all, we obtain a clean and simple deletion decomposition theorem for all H-minor-free graphs that can be used to obtain many approximation algorithms, PTASes, and parameterized algorithms.

Download Video: 360p, 720p

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

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