Proximity graphs: E, δ, Δ, χ and ω

Prosenjit Bose, Vida Dujmovic, Ferran Hurtado, John Lacono, Stefan Langerman, Henk Meijer, Vera Sacristan, Maria Saumell, David Wood

Research output: Contribution to journalArticleResearchpeer-review

18 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)439-469
Number of pages31
JournalInternational Journal of Computational Geometry and Applications
Issue number5
Publication statusPublished - 2012
Externally publishedYes

Cite this