Cone-based spanners of constant degree

We study spanning properties of sparse cone-based graphs of constant degree, parameterized by a positive integer k>1. Cone-based graphs partition the space around each vertex into k equiangular cones, and select at most one outgoing edge in each cone. This guarantees an out-degree of at most k, but the in-degree may be unbounded. To bound the in-degree, at most one incoming edge is retained in each cone. This yields a sparse graph of degree at most 2k (in-degree k and out-degree k). In this paper we introduce the notion of canonical k-cone graphs and establish a spanning ratio of 16.76 for this class of graphs, provided that k=6k′ and k′≥5. The spanning ratio decreases to 4.64 as k′ increases to 8. We show that both Yao-Yao and Theta-Theta graphs are canonical k-cone graphs and therefore they inherit these spanning ratios. Yao-Yao and Theta-Theta graphs differ only in the way edges are selected. Yao-Yao graphs select an edge of minimum Euclidean length, whereas Theta-Theta graphs select an edge of minimum orthogonal projection onto the cone bisector.