On the dilation spectrum of paths, cycles, and trees
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.
|Keywords||Computational geometry, Dilation, Distribution, Geometric graph, Network, Spectrum, Stretch factor|
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