Let G be a graph with n vertices which is embedded in Euclidean space R d. For any two vertices of G, their dilation is defined to be the ratio of the length of a shortest connecting path in G to the Euclidean distance between them. In this paper, we study the spectrum of the dilation, over all pairs of vertices of G. For paths, cycles, and trees in R 2, we present O(n3 /2+)-time randomized algorithms that compute, for a given value κ>1, the exact number of vertex pairs of dilation at most κ. Then we present deterministic algorithms that approximate the number of vertex pairs of dilation at most κ to within a factor of 1+. They run in O(nlog 2n) time for paths and cycles, and in O(nlog 3n) time for trees, in any constant dimension d.

Additional Metadata
Keywords Computational geometry, Dilation, Distribution, Geometric graph, Network, Spectrum, Stretch factor
Persistent URL dx.doi.org/10.1016/j.comgeo.2009.03.004
Journal Computational Geometry
Citation
Klein, R. (Rolf), Knauer, C. (Christian), Narasimhan, G. (Giri), & Smid, M. (2009). On the dilation spectrum of paths, cycles, and trees. In Computational Geometry (Vol. 42, pp. 923–933). doi:10.1016/j.comgeo.2009.03.004