[+] PTAS for planar subsetconnectivity problems I: construction of a mortar graphbrick decomposition and spanner for subset TSP and Steiner tree 
In this lecture we study the breakthrough result of Borradaile, Klein,
and Mathieu regarding a PTAS for Steiner tree in planar
graphs. Steiner tree is a subsettype problem, where we mainly care
about a given subset of terminals in the graph. In particular, the
weight of a Steiner tree can be arbitrarily smaller than the minimum
spanning tree of the graph. This makes it very different from all
problems we have studied so far.
In the previous lecture we got acquainted with Klein's framework for designing PTASes in planar graphs and applied it to the TSP problem. In this lecture, we review this framework and see how to apply it to the Steiner tree problem. We will see that the most difficult step is to obtain a spanner. We study the so called mortar graphbrick decomposition and how it gives rise to a spanner. This decomposition has been applied to further problems as well and has been generalized to boundedgenus graphs. In Lecture 16 we will describe the algorithm and its correctness based on a structure theorem. The structure theorem itself is presented in Lecture 17. 
Lecture notes, page 1/14 •
[previous page] •
[next page] •
[PDF]
Lecture notes, page 1/14 • [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.