Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/26485

Witness rectangle graphs
Aronov, Boris; Dulieu, Muriel; Hurtado Díaz, Fernando Alfredo
Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta
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.
Peer Reviewed
Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta
Graph theory
Proximity graphs
Rectangle of influence graph
Witness graphs
Grafs, Teoria de
info:eu-repo/semantics/publishedVersion
Artículo
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Aronov, Boris; Dulieu, Muriel; Hurtado Díaz, Fernando Alfredo
Taslakian, Perouz; Seara Ojea, Carlos; Saumell Mendiola, Maria; Langerman, Stefan; Hurtado Díaz, Fernando Alfredo; Aloupis, Greg; Cardinal, Jean; Collette, Sébastien; Demaine, Erik D.; Demaine, Martin L.; Dulieu, Muriel; Fabila Monroy, Ruy; Hart, Vi
Agarwal, Pankaj; Aronov, Boris; Kreveld, Marc van; Löffler, Maarten; Silveira, Rodrigo Ignacio
Agarwal, Pankaj; Aronov, Boris; Van Kreveld, Matias; Löffler, Maarten; Silveira, Rodrigo Ignacio
Speckmann, Bettina; Silveira, Rodrigo Ignacio; Aronov, Boris; Buchin, Kevin; Buchin, Maike; Jansen, Bart; De Jong, Tom; Kreveld, Marc van; Loffler, Maarten; Luo, Jun