Cone-Based Graphs

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

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.


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.


Contributed by: Mirela Damian, Kelly Gremban, and Naresh Nelavalli (May 2015)
Supported by NSF grant CCF-1218814.
Open content licensed under CC BY-NC-SA




[1] 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.

Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.