Tree Spanners in Planar Graphs

Fekete, Sandor P. and Kremer, Jana (2001) Tree Spanners in Planar Graphs.
Published in: Discrete Applied Mathematics Vol. 108 (1-2). pp. 85-103.


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.

Download: [img] Postscript - Preprinted Version
Download (424kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr98-313a
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:46