Computing the Detour and Spanning Ratio of Paths, Trees, and Cycles in 2D and 3D

The detour and spanning ratio of a graph G embedded in measure how well G approximates Euclidean space and the complete Euclidean graph, respectively. In this paper we describe O(nlog n) time algorithms for computing the detour and spanning ratio of a planar polygonal path. By generalizing these algorithms, we obtain O(nlog ² n)-time algorithms for computing the detour or spanning ratio of planar trees and cycles. Finally, we develop subquadratic algorithms for computing the detour and spanning ratio for paths, cycles, and trees embedded in , and show that computing the detour in is at least as hard as Hopcroft’s problem. This research was partly funded by CRM, FCAR, MITACS, and NSERC. P.A. was supported by NSF under grants CCR-00-86013 EIA-99-72879, EIA-01-31905, and CCR-02-04118, by ARO grants W911NF-04-1-0278 and DAAD19-03-1-0352, and by a grant from the U.S.-Israeli Binational Science Foundation. R.K. was supported by DFG grant Kl 655/14-1. M.S. was supported by NSF Grants CCR-97-32101 and CCR-00-98246, by a grant from the U.S.-Israeli Binational Science Foundation (jointly with P.A.), by a grant from the Israeli Academy of Sciences for a Center of Excellence in Geometric Computing at Tel Aviv University, and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University. Some of these results have appeared in a preliminary form in 2, 20].