Spanners in sparse graphs

Peter Golovach

Abstract

A t-spanner of a graph G is a spanning subgraph S in which the distance between every pair of vertices is at most t times their distance in G. If S is required to be a tree then S is called a tree t-spanner of G. In 1998, Fekete and Kremer showed that on unweighted planar graphs the Tree t-Spanner problem (the problem to decide whether G admits a tree t-spanner) is polynomial time solvable for t<=3 and is NP-complete as long as t is part of the input. They also left as an open problem whether the Tree t-Spanner problem is polynomial time solvable for every fixed t>=4. In this work we resolve this open problem and extend the solution in several directions. We show that for every fixed t, it is possible in polynomial time not only to decide if a planar graph G has a tree t-spanner, but also to decide if G has a t-spanner of bounded treewidth. Moreover, for every fixed values of t and k, the problem, for a given planar graph G to decide if G