In graph theory, a spanner graph has the property that the length of a shortest path between vertices is no greater than a constant times the spatial distance between the vertices. Cone-based graphs are geometric graphs defined for points in the plane. The space around each point is partitioned into a fixed number of equiangular cones, and a nearest neighbor is selected in each cone. These graphs are known to be spanners for certain values of . Various types of cone-based graphs differ in the way the nearest neighbor is defined.[more]
This Demonstration generates the cone-based graphs of types "Yao," "Theta," and "HalfTheta" for a random plane point set. These graphs are parameterized by an integer value between 3 and 10, representing the number of cones, and include at most 1 outgoing edge per cone. Their sparse variants "YaoYao," "ThetaTheta," and "HalfThetaTheta" include at most 1 incoming edge per cone, in addition to the outgoing edge.[less]
 M. Damian and D. Voicu, "Spanning Properties of Theta-Theta Graphs," in Combinatorial Optimization and Applications, 8th International Conference (Z. Zhang, L. Wu, W. Xu, D. Du, eds.), Springer Science+Business Media, 2014, pp. 216–230.
Wolfram Demonstrations Project
Published: May 26 2015