ON STRUCTURAL AND GRAPH THEORETIC PROPERTIES OF HIGHER ORDER DELAUNAY GRAPHS
Given a set P of n points in the plane, the order-k Delaunay graph is a graph withh vertex set P and an edge exists between two points p, q is an element of 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  = 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.
delaunay graph geometric graphs higher order proximity graphs