On the dilation spectrum of paths, cycles, and trees

Let G be a graph with n vertices which is embedded in Euclidean space Rd. 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 R2, 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(nlog2n) time for paths and cycles, and in O(nlog3n) time for trees, in any constant dimension d.