TY - GEN
T1 - Witness rectangle graphs
AU - Aronov, Boris
AU - Dulieu, Muriel
AU - Hurtado, Ferran
N1 - Funding Information:
Research of B.A. has been partially supported by NSA MSP Grants H98230-06-1-0016 and H98230-10-1-0210. Research of B.A. and M.D. has also been supported by a grant from the U.S.-Israel Binational Science Foundation and by NSF Grant CCF-08-30691. Research by F.H. has been partially supported by projects MEC MTM2006-01267 and MTM2009-07242, and Gen. Catalunya DGR 2005SGR00692 and 2009SGR1040.
PY - 2011
Y1 - 2011
N2 - 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 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 co-interval graph, thereby providing a complete characterization of WRGs of this type. We also completely characterize trees drawable as WRGs. 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.
AB - 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 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 co-interval graph, thereby providing a complete characterization of WRGs of this type. We also completely characterize trees drawable as WRGs. 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.
UR - http://www.scopus.com/inward/record.url?scp=80052128625&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80052128625&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-22300-6_7
DO - 10.1007/978-3-642-22300-6_7
M3 - Conference contribution
AN - SCOPUS:80052128625
SN - 9783642222993
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 73
EP - 85
BT - Algorithms and Data Structures - 12th International Symposium, WADS 2011, Proceedings
T2 - 12th International Symposium on Algorithms and Data Structures, WADS 2011
Y2 - 15 August 2011 through 17 August 2011
ER -