On Rectangle Visibility Graphs

Bose, 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 18-20, 1996 , pp. 25-44(Official URL: http://dx.doi.org/10.1007/3-540-62495-3_35).

Full text not available from this repository.


We 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 lines-of-sight. 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 rectangle-visibility 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 distance-two independent set is an RVG. 4. Any graph with maximum degree four is an RVG. Our proofs are constructive and yield linear-time layout algorithms.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-62495-3_35
Classifications: P Styles > P.900 Visibility
Z Theory > Z.999 Others
G Algorithms and Complexity > G.999 Others
URI: http://gdea.informatik.uni-koeln.de/id/eprint/59

Actions (login required)

View Item View Item