ABSTRACT


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 minimumlength 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 multiplesource shortestpath 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. Return to DMTCS home page. 