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

Full text not available from this repository.

Abstract

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
ID Code:59

Repository Staff Only: item control page

References

T. Biedl. Perconal Communication, 1995.

P. Bose, A. Dean, J. Hutchinson, and T. Shermer. On rectangle visibility graphs I. k-trees and caterpillar forests. Manuscript, 1996.

A. M. Dean and J. P. Hutchinson. Combinatorial representations of visibility graphs. Preprint, 1996.

A. M. Dean and J. P. Hutchinson. Rectangle-visibility representations of bipartite graphs. Discrete Applied Mathematics, 1996, to appear.

P. Duchet, Y. Hamidoune, M. Las Vergnas, and H. Meyniel. Representing a planar graph by vertical lines joining different levels. Diskrete Mathematics, 46:319-321, 1983.

M. R. Garey, D. S. Johnson, and H. C. So. An application of graph coloring to printed circuit testing. IEEE Transactions on Circuits and Systems, CAS-23:591-599,1976.

P. Horak and L. Niepel. A short proof of linear arboricity theorem for cubic graphs. Acta Math. Univ. Comenian., XL-XLI:255-277, 1982.

J. P. Hutchinson, T. Shermer, and A. Vince. On representations of some thickness-two graphs (extended abstract). In F. Brandenburg, editor, Proc. of Workshop on Graph Drawing, volume 1027 of Lecture Notes in Computer Science. Springer-Verlag, 1995.

F. Luccio, S. Mazzone, and C. K. Wong. A note on visibility graphs. Discrete Mathematics, 64:209-219, 1987.

T. C. Shermer. On rectangle visibility graphs II. k-hilly and maximum degree 4. Manuscript, 1996.

T. C. Shermer. On rectangle visibility graphs III. external visibility and complexity. Manuscript, 1996.

R. Tamassia and I. G. Tollis. A unified approach to visibility representations of planar graphs. Discrete and Computational Geometry,1:321-341, 1986.

S. K. Wismath. Characterizing bar line-of-sight graphs. In proc. 1st Symp. Comp. Geom., pages 147-152. ACM, 1985.

S. K. Wismath. Bar-Representable Visibility Graphs and a Related Network Flow Problem. PhD. thesis, Department of Computer Science, University of British Columbia, 1989.