Witness Gabriel graphs

Boris Aronov, Muriel Dulieu, Ferran Hurtado

    Research output: Contribution to journalArticle


    We consider a generalization of the Gabriel graph, the witness Gabriel graph. Given a set of vertices P and a set of witness points W in the plane, there is an edge ab between two points of P in the witness Gabriel graph GG-(P,W) if and only if the closed disk with diameter ab does not contain any witness point (besides possibly a and/or b). We study several properties of the witness Gabriel graph, both as a proximity graph and as a new tool in graph drawing.

    Original languageEnglish (US)
    Pages (from-to)894-908
    Number of pages15
    JournalComputational Geometry: Theory and Applications
    Issue number7
    StatePublished - 2013


    • Gabriel graph
    • Graph drawing
    • Proximity graph
    • Witness graph

    ASJC Scopus subject areas

    • Computer Science Applications
    • Geometry and Topology
    • Control and Optimization
    • Computational Theory and Mathematics
    • Computational Mathematics

    Fingerprint Dive into the research topics of 'Witness Gabriel graphs'. Together they form a unique fingerprint.

  • Cite this