# Observatorio de I+D+i UPM

Memorias de investigación
Artículos en revistas:
On Structural and graph theoretic properties of higher order Delaunay graphs
Año:2007
Áreas de investigación
Datos
Descripción
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 \in 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\leq 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 \geq 0$. We show that the order-$k$ Gabriel graph, a subgraph of the order-$k$ Delaunay graph, is Hamiltonian for $k\geq 15$. Finally, the order-$k$ Delaunay graph can be used to efficiently solve a coloring problem with applications to frequency assignments in cellular networks.
Internacional
Si
JCR del ISI
Si
Título de la revista
INT J COMPUT GEOM AP
ISSN
0218-1950
Factor de impacto JCR
0,298
Información de impacto
Volumen
--
DOI
Número de revista
0
Desde la página
--
Hasta la página
--
Mes
SIN MES
Ranking
Esta actividad pertenece a memorias de investigación
Participantes
• Autor: A. RAMOS (U. ALCALÁ HENARES)
• Autor: M. ABELLANAS (UPM)
• Autor: C.M. NICOLÁS
• Autor: Jesus Garcia Lopez de Lacalle (UPM)
• Autor: B. PROSENJIT