6.889: Algorithms for Planar Graphs and Beyond (Fall 2011)

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!