On a visibility representation for graphs in three dimensions

Bose, Prosenjit K. and Everett, Hazel and Fekete, Sandor P. and Lubiw, Anna and Meijer, Henk and Romanik, Kathleen A. and Shermer, Thomas C. and Whitesides, Sue (1993) On a visibility representation for graphs in three dimensions.
Published In: Graph drawing : 9th international symposium ; ALCOM International Workshop Paris 1993 on Graph Drawing and Topological Graph Algorithms Alcom 1993, pp. 38-39.


Visibility representations of graphs map vertices to sets in Euclidean space and express edges as visibility relations between these sets. Application areas such as VLSI wire routing and circuit board layout have stimulated research on visibility representations where the sets belong to R 2 . Here, motivated by the emerging research area of graph drawing, we study a 3-dimensional visibility representation. In this representation, each vertex of the graph maps to a closed rectangle in R 3 such that the rectangles are disjoint, the planes determined by the rectangles are perpendicular to the z-axis, and the sides of the rectangles are parallel to the x- or y-axes. Edges are expressed by the following visibility relation. Two rectangles Ri and Rj are considered visible provided that there exists a closed cylinder C of non-zero radius such that the ends of C are contained in Ri and Rj, the axis of C is parallel to the z-axis, and C does not intersect any other rectangle. Our main results are as follows. All planar graphs have a representation, as do many non-planar graphs. In particular, a complete graph Kn has a representation for values of n<=20. However, a complete graph Kn does not have a representation for n>=103. (Recently, this bound has been improved to 56 by Fekete, Houle, and Whitesides, using extensions of the techniques presented here.) The complete bipartite graph Km,n has a representation for all m and n. Finally, we show that the family of graphs with a representation is not closed under graph minors. This is an extended version of the published paper.

Download: [img] Postscript - Preprinted Version
Download (285kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr95-205
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Jan 2012 11:25
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/205