We consider the problem of augmenting an n-vertex graph embedded in a metric space, by inserting one additional edge in order to minimize the diameter of the resulting graph. We present exact algorithms for the cases when (i) the input graph is a path, running in O(n ^3 n) time, and (ii) the input graph is a tree, running in O(n^2 n) time. We also present an algorithm that computes a (1+ )-approximation in O(n + 1 ^3) time, for paths in R^d, where d is a constant.
 Given a graph embedded in a metric space, its dilation is the maximum over all distinct pairs of vertices of the ratio between their distance in the graph and the metric distance between them. Given such a graph G with n vertices and m edges and consisting of at most two connected components, we consider the problem of augmenting G with an edge such that the resulting graph has minimum dilation. We show that we can find such an edge in @math time using linear space which solves an open problem of whether a linear-space algorithm with o(n 4) running time exists. We show that O(n 2logn) time is achievable if G is a simple path or the union of two vertex-disjoint simple paths. Finally, we show how to find an edge that maximizes the dilation of the resulting graph in O(n 3) time with O(n 2) space and in O(n 3logn) time with linear space. Let G=(V,E) be an undirected graph with n vertices embedded in a metric space. We consider the problem of adding a shortcut edge in G that minimizes the dilation of the resulting graph. The fastest algorithm to date for this problem has O(n^4) running time and uses O(n^2) space. We show how to improve the running time to O(n^3logn) while maintaining quadratic space requirement. In fact, our algorithm not only determines the best shortcut but computes the dilation of [email protected]? (u,v) for every pair of distinct vertices u and v. Given a Euclidean graph @math in @math with @math vertices and @math edges, we consider the problem of adding an edge to @math 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 @math @math time, resulting in a trivial @math @math -time algorithm for computing the optimal edge. First, we show that a simple modification yields the optimal solution in @math @math time using @math @math space. To reduce the running time we consider several approximation algorithms.