Witness rectangle graphs

DOI10.1007/S00373-013-1316-XzbMATH Open1298.05091arXiv1108.2058OpenAlexW1819541087MaRDI QIDQ742595FDOQ742595

Authors: Boris Aronov, Muriel Dulieu, Ferran Hurtado 

Publication date: 19 September 2014

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1108.2058

Recommendations

• Witness rectangle graphs
• Witness (Delaunay) graphs
• Witness Gabriel graphs
• Mutual witness proximity graphs
• Finding minimum witness sets in orthogonal polygons

zbMATH Keywords

proximity graphswitness graphsrectangle of influence graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Title not available (Why is that?)
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Moore graphs and beyond: a survey of the degree/diameter problem
• On empty triangles determined by points in the plane
• Covering the convex quadrilaterals of point sets
• Maximum degree in graphs of diameter 2
• Title not available (Why is that?)
• A note on large graphs of diameter two and given maximum degree
• Witness Gabriel graphs
• Witness rectangle graphs
• Witness (Delaunay) graphs
• The strength of weak proximity
• Domination in planar graphs with small diameter II.
• Domination in planar graphs with small diameter*
• Separating pairs of points of standard boxes
• The rectangle of influence drawability problem
• Title not available (Why is that?)
• Closed rectangle-of-influence drawings for irreducible triangulations
• Delaunay graphs of point sets in the plane with respect to axis‐parallel rectangles
• The relative neighborhood graph for mixed feature variables
• A general approach to dominance in the plane
• Decompositions into subgraphs of small diameter
• Open rectangle-of-influence drawings of inner triangulated plane graphs
• On Open Rectangle-of-Influence Drawings of Planar Graphs
• Graphs with small diameter after edge deletion
• Title not available (Why is that?)

Cited In (8)

• Mutual witness proximity drawings of isomorphic trees
• Mutual witness proximity graphs
• Mutual witness Gabriel drawings of complete bipartite graphs
• Witness Gabriel graphs
• Witness (Delaunay) graphs
• Witness rectangle graphs
• Mutual witness Gabriel drawings of complete bipartite graphs
• The Mathematics of Ferran Hurtado: A Brief Survey

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)