20020101
On the spanning ratio of gabriel graphs and βskeletons
Publication
Publication
The spanning ratio of a graph defined on n points in the Euclidean plane is the maximal ratio over all pairs of data points (u, v), of the minimum graph distance between u and v, over the Euclidean distance between u and v. A connected graph is said to be a kspanner if the spanning ratio does not exceed k. For example, for any k, there exists a point set whose minimum spanning tree is not a kspanner. At the other end of the spectrum, a Delaunay triangulation is guaranteed to be a 2.42spanner[11]. For proximity graphs inbetween these two extremes, such as Gabriel graphs[8], relative neighborhood graphs[16] and βskeletons[12] with β ∈ [0, 2] some interesting questions arise. We show that the spanning ratio for Gabriel graphs (which are βskeletons with β = 1) is Θ(Equation Presented) in the worst case. For all βskeletons with β ∈ [0, 1], we prove that the spanning ratio is at most O(n<sup>γ</sup>) where γ = (1 − log<inf>2</inf>(Equation Presented))/2. For all βskeletons with β ∈ [1, 2), we prove that there exist point sets whose spanning ratio is at least (Equation Presented). For relative neighborhood graphs[16] (skeletons with β = 2), we show that there exist point sets where the spanning ratio is Ω(n). For points drawn independently from the uniform distribution on the unit square, we show that the spanning ratio of the (random) Gabriel graph and all βskeletons with β ∈ [1, 2] tends to ∞ in probability as (Equation Presented).
Additional Metadata  

Citation 
Bose, P, Devroye, L. (Luc), Evans, W. (William), & Kirkpatrick, D. (David). (2002). On the spanning ratio of gabriel graphs and βskeletons.
