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

Prosenjit Bose, Vida Dujmović, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Vera Sacristán, Maria Saumell, David R. Wood

    Research output: Contribution to journalArticlepeer-review


    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 (US)
    Pages (from-to)439-469
    Number of pages31
    JournalInternational Journal of Computational Geometry and Applications
    Issue number5
    StatePublished - Oct 2012


    • Geometric graphs
    • graph-theoretic properties
    • proximity graphs

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Computational Theory and Mathematics
    • Computational Mathematics
    • Applied Mathematics


    Dive into the research topics of 'Proximity graphs: E, δ, Δ, χ and ω'. Together they form a unique fingerprint.

    Cite this