2006
On spanners of geometric graphs
Publication
Publication
Given a connected geometric graph G, we consider the problem of constructing a tspanner of G having the minimum number of edges. We prove that for every t with 1 < t < 1/4 log n, there exists a connected geometric graph G with n vertices, such that every tspanner of G contains Ω(n <sup>1+1/t</sup>) edges. This bound almost matches the known upper bound, which states that every connected weighted graph with n vertices contains a tspanner with O(tn<sup>1+2/(t+1)</sup>) edges. We also prove that the problem of deciding whether a given geometric graph contains a tspanner with at most K edges is NPhard. Previously, this NPhardness result was only known for nongeometric graphs.
Additional Metadata  

dx.doi.org/10.1007/11785293_36  
Organisation  Computational Geometry Lab 
Gudmundsson, J. (Joachim), & Smid, M. (2006). On spanners of geometric graphs. doi:10.1007/11785293_36
