Tree spanners in planar graphs

A tree t-spanner of a graph G is a spanning subtree T of G in which the dis tance between every pair of vertices is at most t times their distance in G . Spanner problems have received some attention, mostly in the context of c ommunication networks. It is known that for general unweighted graphs, the problem of deciding the existence of a tree t-spanner can be solved in poly nomial time for t = 2, while it is NP-hard for any t greater than or equal to4; the case t = 3 is open, but has been conjectured to be hard. In this p aper, we consider tree spanners in planar graphs. We show that even for pla nar unweighted graphs, it is NP-hard to determine the minimum t for which a tree t-spanner exists. On the other hand, we give a polynomial algorithm f or any fixed t that decides for planar unweighted graphs with bounded face length whether there is a tree t-spanner. Furthermore, we prove that it can be decided in polynomial time whether a planar unweighted graph has a tree t-spanner for t = 3. (C) 2001 Elsevier Science B.V. All rights reserved.