Abstract. Given a Euclidean graph G in R d with n vertices and m edges, we consider the problem of adding an edge to G such that the stretch factor of the resulting graph is minimized. Currently, the fastest algorithm for computing the stretch factor of a graph with positive edge weights runs in O(nm + n 2 log n) time, resulting in a trivial O(n 3 m + n 4 log n)-time algorithm for computing the optimal edge. First, we show that a simple modification yields the optimal solution in O(n 4 ) time using O(n 2 ) space. To reduce the running time we consider several approximation algorithms. Key words. computational geometry, approximation algorithms, geometric networks AMS subject classifications. 65D18, 68U05, 68Q25 DOI. 10.1137/050635675 1. Introduction. Consider a set V of n points in R d . A network on V can be modeled as an undirected graph G with vertex set V of size n and an edge set E of size m where every edge (u, v) has a positive weight w (u, v). A Euclidean network is a geometric network where the weight of the edge (u, v) is equal to the Euclidean distance |uv| between its two endpoints u and v. For two vertices u, v in a weighted graph G we use δ G (u, v) to denote a shortest path between u and v in G, and the length of the path is denoted by d G (u, v). Consider a weighted graph G = (V, E) and a graph G = (V, E ) on the same vertex set but with edge set E ⊆ E. We say that G is a t-spanner of G if for each pair of vertices (u, v). The minimum t such that G is a t-spanner for V is called the stretch factor, or dilation, of G. We say that a Euclidean network G = (V, E) is a t-spanner if G = (V, E) is a t-spanner of the complete network on V . In other words, for any two points p, q ∈ V the graph distance in G is at most t times the Euclidean distance between the two points. Complete graphs represent ideal communication networks, but they are expensive to build; sparse spanners represent low-cost alternatives. The weight of the spanner network is a measure of its sparseness; other sparseness measures include the number of edges, the maximum degree, and the number of Steiner points. Spanners for complete Euclidean graphs as well as for arbitrary weighted graphs find applications in robotics, network topology design, distributed systems, design of parallel machines, and many other areas. Recently spanners found interesting practical applications
Farshi et al. REF show that it is possible to compute, for a given geometric graph, the edge that results in the largest dilation reduction in O(n 4 ) time.
Improving the Stretch Factor of a Geometric Network by Edge Augmentation
SIAM J. Comput.
SIAM J. Comput.
Computer Science Mathematics