Fekete, Sandor P. and Kremer, Jana (1998) Tree Spanners in Planar Graphs.
Published In: Graph theoretic concepts in computer science : 24th international workshop ; proceedings / WG '98, Smolenice Castle, Slovak Republic, June 18 - 20, 1998 , Lecture notes in computer science. 1517 Springer 1998, pp. 9-30.

Abstract

A tree t-spanner of a graph G is a spanning subtree H of G in which the distance 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 communication networks. It is known that for general unweighted graphs, the existence of a tree 2-spanner can be decided in polynomial time, while it is NP-hard to decide whether a tree 4-spanner exists; the case t=3 is open, but has been conjectured to be hard. In this paper, we consider tree spanners in planar graphs. We show that even for planar graphs, it is NP-hard to determine the minimum t for which a tree t-spanner exists. On the other hand, we prove that it can be decided in polynomial time whether a planar graph has a tree t-spanner for t=3, and we give a polynomial algorithm for determining the minimum t for planar graphs with bounded face lengths.

Actions:

Download:	Postscript - Preprinted Version Download (252kB) | Preview
Editorial actions:	View Item (Login required)