Observatorio de I+D+i UPM

Memorias de investigación
Research Publications in journals:
On Structural and graph theoretic properties of higher order Delaunay graphs
Year:2007
Research Areas
  • Architecture of computers
Information
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 \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.
International
Si
JCR
Si
Title
INT J COMPUT GEOM AP
ISBN
0218-1950
Impact factor JCR
0,298
Impact info
Volume
--
Journal number
0
From page
--
To page
--
Month
SIN MES
Ranking
Participants
  • 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
  • Autor: F. HURTADO (UPC)
Research Group, Departaments and Institutes related
  • Creador: Departamento: Matemática Aplicada (E.U. Informática)
S2i 2019 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)