Let G be a graph embedded in Euclidean space. For any two vertices of G their dilation denotes the length of a shortest connecting path in G, divided by their Euclidean distance. In this paper we study the spectrum of the dilation, over all pairs of vertices of G. For paths, trees, and cycles in 2D we present O(n3/2+ε) randomized algorithms that compute, for a given value k ≥ 1, the exact number of vertex pairs of dilation > k. Then we present deterministic algorithms that approximate the number of vertex pairs of dilation > k up to an 1 + η factor. They run in time O(n log 2n) for chains and cycles, and in time O(n log3 n) for trees, in any constant dimension.

Additional Metadata
Persistent URL dx.doi.org/10.1007/11602613_85
Citation
Klein, R. (Rolf), Knauer, C. (Christian), Narasimhan, G. (Giri), & Smid, M. (2005). Exact and approximation algorithms for computing the dilation spectrum of paths, trees, and cycles. doi:10.1007/11602613_85