Witness rectangle graphs
From MaRDI portal
Abstract: In a witness rectangle graph (WRG) on vertex point set P with respect to witness points 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 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 point.
Recommendations
Cites work
- scientific article; zbMATH DE number 2123123 (Why is no real title available?)
- scientific article; zbMATH DE number 193423 (Why is no real title available?)
- scientific article; zbMATH DE number 1055145 (Why is no real title available?)
- scientific article; zbMATH DE number 1500691 (Why is no real title available?)
- A general approach to dominance in the plane
- A note on large graphs of diameter two and given maximum degree
- Closed rectangle-of-influence drawings for irreducible triangulations
- Covering the convex quadrilaterals of point sets
- Decompositions into subgraphs of small diameter
- Delaunay graphs of point sets in the plane with respect to axis‐parallel rectangles
- Domination in planar graphs with small diameter II.
- Domination in planar graphs with small diameter*
- Graphs with small diameter after edge deletion
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Maximum degree in graphs of diameter 2
- Moore graphs and beyond: a survey of the degree/diameter problem
- On Open Rectangle-of-Influence Drawings of Planar Graphs
- On empty triangles determined by points in the plane
- Open rectangle-of-influence drawings of inner triangulated plane graphs
- Separating pairs of points of standard boxes
- The rectangle of influence drawability problem
- The relative neighborhood graph for mixed feature variables
- The strength of weak proximity
- Witness (Delaunay) graphs
- Witness Gabriel graphs
- Witness rectangle graphs
Cited in
(8)- Witness rectangle graphs
- Witness Gabriel graphs
- The Mathematics of Ferran Hurtado: A Brief Survey
- Mutual witness proximity graphs
- Mutual witness proximity drawings of isomorphic trees
- Mutual witness Gabriel drawings of complete bipartite graphs
- Witness (Delaunay) graphs
- Mutual witness Gabriel drawings of complete bipartite graphs
This page was built for publication: Witness rectangle graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q742595)
