Graph-theoretic properties of certain proximity graphs defined on planar point sets are investigated. We first consider some of the most common proximity graphs of the family of the Delaunay graph, and study their number of edges, minimum and maximum degree, clique number, and chromatic number. In the second part of the paper we focus on the higher order versions of some of these graphs and give bounds on the same parameters.

Additional Metadata
Keywords Geometric graphs, graph-theoretic properties, proximity graphs
Persistent URL
Journal International Journal of Computational Geometry and Applications
Bose, P, Dujmović, V, Hurtado, F. (Ferran), Iacono, J. (John), Langerman, S. (Stefan), Meijer, H. (Henk), … Wood, D. (2012). Proximity graphs: E, δ, Δ, χ and ω. International Journal of Computational Geometry and Applications, 22(5), 439–469. doi:10.1142/S0218195912500112