Tree Spanners in Planar Graphs
Fekete, Sandor P. and Kremer, Jana
(2001)
Tree Spanners in Planar Graphs.
Published in:
Discrete Applied Mathematics Vol. 108 (12).
pp. 85103.
Abstract
A tree tspanner 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 2spanner can be decided in polynomial time, while it is NPhard to decide whether a tree 4spanner 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 NPhard to determine the minimum t for which a tree tspanner exists. On the other hand, we prove that it can be decided in polynomial time whether a planar graph has a tree tspanner for t=3, and we give a polynomial algorithm for determining the minimum t for planar graphs with bounded face lengths.
Download: 
Postscript
 Preprinted Version
Download (424kB)  Preview 

Editorial actions:  View Item (Login required) 
Item Type:  Article 

Citations:  46 (Google Scholar)  29 (Web of Science) 
Uncontrolled Keywords:  complexity distance in graphs graph spanners planar graphs polynomial algorithms subgraphs trees 
Subjects: 

Divisions:  Mathematical Institute 
Related URLs: 
ZAIK Number:  zpr98313a 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  19 Dec 2011 09:46 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/313001 