On Rectangle Visibility GraphsBose, Prosenjit and Dean, Alice M. and Hutchinson, Joan P. and Shermer, Thomas (1997) On Rectangle Visibility Graphs. In: Symposium on Graph Drawing, GD '96, September 1820, 1996 , pp. 2544(Official URL: http://dx.doi.org/10.1007/3540624953_35). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540624953_35
AbstractWe study the problem of drawing a graph in the plane so that the vertices of the graph are rectangles that are aligned with the axes, and the edges of the graph are horizontal or vertical linesofsight. Such a drawing is usefull, for example, when the vertices of the graph contain information that we wish displayed on the drawing; it is natural to write this information inside the rectangle corresponding to the vertex. We call a graph that can be drawn in this fashion a rectanglevisibility graph, or RVG. Our goal is to find classes of graphs that are RVGs. We obtain several results: 1. For 1<= k <=4, trees are RVGs. 2. Any Graph that can be decomposed into two caterpillar forests is an RVG. 3. Any graph whose vertices of degree four or more form a distancetwo independent set is an RVG. 4. Any graph with maximum degree four is an RVG. Our proofs are constructive and yield lineartime layout algorithms.
Actions (login required)
