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 journalArticle

    Abstract

    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
    Volume22
    Issue number5
    DOIs
    StatePublished - Oct 2012

    Keywords

    • 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

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

  • Cite this

    Bose, P., Dujmović, V., Hurtado, F., Iacono, J., Langerman, S., Meijer, H., Sacristán, V., Saumell, M., & Wood, D. R. (2012). Proximity graphs: E, δ, Δ, χ and ω. International Journal of Computational Geometry and Applications, 22(5), 439-469. https://doi.org/10.1142/S0218195912500112