Witness Rectangle Graphs

Boris Aronov, Muriel Dulieu, Ferran Hurtado

    Research output: Contribution to journalArticlepeer-review


    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


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

    Cite this