[+] Steiner tree in bounded genus graphs / Beyond Hminorfree: Overview of (sparse) graph classes. 
In this lecture we introduce the notion of a treecotree 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 Hminorfree 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 Hminorfree graphs! 
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.