Back to Search
Start Over
ON STRUCTURAL AND GRAPH THEORETIC PROPERTIES OF HIGHER ORDER DELAUNAY GRAPHS.
- Source :
-
International Journal of Computational Geometry & Applications . Dec2009, Vol. 19 Issue 6, p595-615. 21p. 9 Diagrams. - Publication Year :
- 2009
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPH theory
*TRIANGULATION
*CIRCLE
*HAMILTONIAN systems
*GRAPHIC methods
Subjects
Details
- Language :
- English
- ISSN :
- 02181959
- Volume :
- 19
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- International Journal of Computational Geometry & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 47377909
- Full Text :
- https://doi.org/10.1142/S0218195909003143