Given a connected geometric graph G, we consider the problem of constructing a t-spanner of G having the minimum number of edges. We prove that for every real number t with $1 < t < {1 \over 4}{\rm{log }}\,n$, there exists a connected geometric graph G with n vertices, such that every t-spanner of G contains Ω(n1+1/t) edges. This bound almost matches the known upper bound, which states that every connected weighted graph with n vertices contains a t-spanner with O(n1+2/(t-1)) edges. We also prove that the problem of deciding whether a given geometric graph contains a t-spanner with at most K edges is NP-hard. Previously, this NP-hardness result was only known for non-geometric graphs.

, ,
International Journal of Foundations of Computer Science
Computational Geometry Lab

Gudmundsson, J. (Joachim), & Smid, M. (2009). On spanners of geometric graphs. International Journal of Foundations of Computer Science, 20(1), 135–149. doi:10.1142/S0129054109006486