Some properties of higher order delaunay and gabriel graphs
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, 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.
|Conference||22nd Annual Canadian Conference on Computational Geometry, CCCG 2010|
Bose, P, Collette, S. (Sébastien), Hurtado, F. (Ferran), Korman, M. (Matias), Langerman, S. (Stefan), Sacristán, V. (Vera), & Saumell, M. (Maria). (2010). Some properties of higher order delaunay and gabriel graphs. Presented at the 22nd Annual Canadian Conference on Computational Geometry, CCCG 2010.