Euclidean Bottleneck Bounded-Degree Spanning Tree Ratios
Ahmad Biniaz · Discrete & Computational Geometry · 2019
Inspired by the seminal works of Khuller et al. (STOC 1994) and Chan (SoCG 2003) we study the bottleneck version of the Euclidean bounded-degree spanning tree problem. A bottleneck spanning tree is a spanning tree whose largest edge-length is minimum, and a bottleneck degree-K spanning tree is a degree-K spanning tree whose largest edge-length is minimum. Let βκ be the supremum ratio of the largest edge-length of the bottleneck degree-K spanning tree to the largest edge-length of the bottleneck spanning tree, over all finite point sets in the Euclidean plane. It is known that β5= 1, and it is easy to verify that , and β4 > 1.175. It is implied by the Hamiltonicity of the cube of the bottleneck spanning tree that β2 ≪ 3. The degree-3 spanning tree algorithm of Ravi et al. (STOC 1993) implies that β3 ≪ 2. Andersen and Ras (Networks, 68(4):302–314, 2016) showed that . We present the following improved bounds: , and . As a result, we obtain better approximation algorithms for Euclidean bottleneck degree-3 and degree-4 spanning trees. As parts of our proofs of these bounds we present some structural properties of the Euclidean minimum spanning tree which are of independent interest.