Some properties of k-Delaunay and k-Gabriel graphs |
| |
| Authors: | Prosenjit Bose Sébastien Collette Ferran Hurtado Matias Korman Stefan Langerman Vera Sacristán Maria Saumell |
| |
| Institution: | 1. School of Computer Science, Carleton University, Ottawa, Canada;2. Computer Science Department, Université Libre de Bruxelles, Brussels, Belgium;3. Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Barcelona, Spain;4. Department of Applied Mathematics, Charles University, Prague, Czech Republic |
| |
| Abstract: | 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
