## Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 827-846 |

Number of pages | 20 |

Journal | Graphs and Combinatorics |

Volume | 30 |

Issue number | 4 |

DOIs | |

State | Published - Jun 2014 |

## Keywords

- Proximity graphs
- Rectangle of influence graph
- Witness graphs

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics