Computer Science – Computational Geometry
Scientific paper
2011-08-09
Computer Science
Computational Geometry
In Proceedings of the 12th International Symposium on Algorithms and Data Structures (WADS), p.73-85, August 2011, New York, N
Scientific paper
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.
Aronov Boris
Dulieu Muriel
Hurtado Ferran
No associations
LandOfFree
Witness Rectangle Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Witness Rectangle Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Witness Rectangle Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-663575