Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Some properties of k-Delaunay and k-Gabriel graphs

Autor
Bose, P.; Collette, S.; Hurtado, F.; Korman, M.; Langerman, S.; Sacristán, V.; Saumell, M.
Tipus d'activitat
Article en revista
Revista
Computational geometry: theory and applications
Data de publicació
2013-02
Volum
46
Número
2
Pàgina inicial
131
Pàgina final
139
DOI
https://doi.org/10.1016/j.comgeo.2012.04.006 Obrir en finestra nova
URL
http://dx.doi.org/10.1016/j.comgeo.2012.04.006 Obrir en finestra nova
Resum
We consider two classes of higher order proximity graphs defined on a set of points in the plane, namely, the k-Delaunay graph and the k-Gabriel graph. We give bounds on the following combinatorial and geometric properties of these graphs: spanning ratio, diameter, connectivity, chromatic number, and minimum number of layers necessary to partition the edges of the graphs so that no two edges of the same layer cross.
Paraules clau
Geometric graphs, Proximity graphs
Grup de recerca
CGA -Computational Geometry and Applications
DCG - Discrete and Combinatorial Geometry

Participants

  • Bose, Prosenjit  (autor)
  • Collette, Sébastien  (autor)
  • Hurtado Diaz, Fernando Alfredo  (autor)
  • Korman Cozzetti, Matias  (autor)
  • Langerman, Stefan  (autor)
  • Sacristán Adinolfi, Vera  (autor)
  • Saumell, Maria  (autor)