Witness Rectangle Graphs

Boris Aronov, Muriel Dulieu, Ferran Hurtado

    Research output: Contribution to journalArticle


    In a witness rectangle graph (WRG) on vertex point set P with respect to witness point set W in the plane, two points x, y in P are adjacent whenever the open isothetic rectangle with x and y as opposite corners contains at least one point in W. WRGs are representative of a larger family of witness proximity graphs introduced in two previous papers. We study graph-theoretic properties of WRGs. We prove that any WRG has at most two non-trivial connected components. We bound the diameter of the non-trivial connected components of a WRG in both the one-component and two-component cases. In the latter case, we prove that a graph is representable as a WRG if and only if each component is a connected co-interval graph, thereby providing a complete characterization of WRGs of this type. We also completely characterize trees drawable as WRGs. In addition, we prove that a WRG with no isolated vertices has domination number at most four. Moreover, we show that any combinatorial graph can be drawn as a WRG using a combination of positive and negative witnesses. Finally, we conclude with some related results on the number of points required to stab all the rectangles defined by a set of n points.

    Original languageEnglish (US)
    Pages (from-to)827-846
    Number of pages20
    JournalGraphs and Combinatorics
    Issue number4
    StatePublished - Jun 2014


    • Proximity graphs
    • Rectangle of influence graph
    • Witness graphs

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Discrete Mathematics and Combinatorics

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

  • Cite this

    Aronov, B., Dulieu, M., & Hurtado, F. (2014). Witness Rectangle Graphs. Graphs and Combinatorics, 30(4), 827-846. https://doi.org/10.1007/s00373-013-1316-x