A planar-graph decomposition, and its application to TSP and Steiner Tree

I describe a decomposition of an undirected planar graph.  I show
that, using this decomposition, one can
- resolve a conjecture of Arora et al. from 1998 concerning the
existence of a certain kind of spanner in planar graphs;
- give an approximation scheme for the problem of finding a
minimum-length tour visiting selected vertices of a planar graph;
- give an approximation scheme for the Steiner tree problem in planar
graphs (joint work with Glencora Borradaile and Claire Mathieu).

Using a multiple-source shortest-path
algorithm for planar graphs, I show that the decomposition can be
constructed in O(n log n) time.  As a consequence, the spanner
construction and the approximation schemes take O(n log n) time.