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

[+] Steiner tree in bounded genus graphs / Beyond H-minor-free: Overview of (sparse) graph classes.

In this lecture we introduce the notion of a tree-cotree decomposition for bounded genus graphs (analogous to interdigitating trees in planar graphs) and use it to obtain a spanner for Steiner tree in bounded genus graphs. Together with the contraction decomposition theorem of Lecture 23 and Klein's PTAS framework, this results in an O(n log n) PTAS for Steiner tree in bounded genus graphs.

Afterwards, we draw a bigger picture of all graph classes we have studied so far and take a peek at graph classes beyond H-minor-free graphs, in particular, classes of bounded expansion and nowhere dense classes of graphs. To understand these classes, we introduce the notion of shallow minors.

Indeed, structural graph theory does not end at H-minor-free graphs!

Download Video: 360p, 720p

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

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