We consider two classes of higher order proximity graphs defined on a set of points in the plane, namely, the k-Delaunay graph and the k-Gabriel graph. We give bounds on the following combinatorial and geometric properties of these graphs: spanning ratio, diameter, connectivity, chromatic number, and minimum number of layers necessary to partition the edges of the graphs so that no two edges of the same layer cross.

Additional Metadata
Keywords Geometric graphs, Proximity graphs
Persistent URL dx.doi.org/10.1016/j.comgeo.2012.04.006
Journal Computational Geometry
Bose, P, Collette, S. (Sébastien), Hurtado, F. (Ferran), Korman, M. (Matias), Langerman, S. (Stefan), Sacristán, V. (Vera), & Saumell, M. (Maria). (2013). Some properties of k-Delaunay and k-Gabriel graphs. In Computational Geometry (Vol. 46, pp. 131–139). doi:10.1016/j.comgeo.2012.04.006