On a visibility representation for graphs in 3D

Bose, Prosenjit K. and Everett, Hazel and Fekete, Sandor P. and Houle, Michael and Lubiw, Anna and Meijer, Henk and Romanik, Kathleen A. and Rote, Günter and Shermer, Thomas C. and Whitesides, Sue and Zelle, Christian (1998) On a visibility representation for graphs in 3D.
Published in: Journal of Graph Algorithms and Applications Vol. 2 (3). pp. 1-16.


This paper proposes a 3-dimensional visibility representation of graphs G = (V,E) in which vertices are mapped to rectangles floating in R 3 parallel to the x,y-plane, with edges represented by vertical lines of sight. We apply an extension of the Erdös-Szekeres Theorem in a geometric setting to obtain an upper bound of n = 56 for the largest representable complete graph Kn. On the other hand, we show by construction that n>=22. These are the best existing bounds. We also note that planar graphs and complete bipartite graphs Km,n are representable, but that the family of representable graphs is not closed under graph minors.

Download: [img] Postscript - Preprinted Version
Download (2MB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr97-253
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 16 Jan 2012 15:34
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/253