Proximity graphs: E, δ, Δ, χ and ω
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.
|Keywords||Geometric graphs, graph-theoretic properties, proximity graphs|
|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