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 twovertices of G, their dilation is defined to be the ratio of the length of a shortest connectingpath in G to the Euclidean distance between them. In this paper, we study the spectrumof the dilation, over all pairs of vertices of G. For paths, cycles, and trees in R2, we present0(n~(3/2+6))-time randomized algorithms that compute, for a given valueK >1, the exactnumber of vertex pairs of dilation at most K. Then we present deterministic algorithmsthat approximate the number of vertex pairs of dilation at most K to within a factor of1 +6. They run in 0(n log~2n)time for paths and cycles, in 0(n log3n)trees,in any constant dimension d.