Area, Perimeter, Height, and Width of Rectangle Visibility Graphs
John S. Caughman, Charles L. Dunn, Joshua D. Laison, Nancy Ann Neudauer, Colin Starr · arXiv (Cornell University) · 2022
A rectangle visibility graph (RVG) is represented by assigning to each vertex a rectangle in the plane with horizontal and vertical sides in such a way that edges in the graph correspond to unobstructed horizontal and vertical lines of sight between their corresponding rectangles. To discretize, we consider only rectangles whose corners have integer coordinates. For any given RVG, we seek a representation with smallest bounding box as measured by its area, perimeter, width, or height (height is assumed not to exceed width). We derive a number of results regarding these parameters. Using these results, we show that these four measures are distinct, in the sense that there exist graphs $G_1$ and $G_2$ with $area(G_1)