Given a set P of n points in the plane, the order-k Delaunay graph is a graph with vertex set P and an edge exists between two points p, q ∈ P when there is a circle through p and q with at most k other points of P in its interior. We provide upper and lower bounds on the number of edges in an order-k Delaunay graph. We study the combinatorial structure of the set of triangulations that can be constructed with edges of this graph. Furthermore, we show that the order-k Delaunay graph is connected under the flip operation when k ≤ 1 but not necessarily connected for other values of k. If P is in convex position then the order-k Delaunay graph is connected for all k < 0. We show that the order-k Gabriel graph, a subgraph of the order-k Delaunay graph, is Hamiltonian for k ≥ 15. Finally, the order-k Delaunay graph can be used to efficiently solve a coloring problem with applications to frequency assignments in cellular networks.

Additional Metadata
Keywords Delaunay graph, Geometric graphs, Higher order proximity graphs
Persistent URL dx.doi.org/10.1142/S0218195909003143
Journal International Journal of Computational Geometry and Applications
Citation
Abellanas, M. (Manuel), Bose, P, García, J. (Jesús), Hurtado, F. (Ferran), Nicolás, C.M. (Carlos M.), & Ramos, P. (Pedro). (2009). On structural and graph theoretic properties of higher order delaunay graphs. International Journal of Computational Geometry and Applications, 19(6), 595–615. doi:10.1142/S0218195909003143