New results on a visibility representation of graphs in 3D
Fekete, Sandor P. and Houle, Michael and Whitesides, Sue
(1996)
New results on a visibility representation of graphs in 3D.
Published In:
Graph drawing : Symposium on Graph Drawing, GD '95, Passau, Germany, September 20  22, 1995 ; proceedings, Lecture notes in computer science. 1027 Springer 1996, pp. 234241.
Abstract
This paper considers a 3dimensional visibility representation of cliques Kn. In this representation, the objects representing the vertices are 2dimensional and lie parallel to the x,yplane, and two vertices of the graph are adjacent if and only if their corresponding objects see each other by a line of sight parallel to the zaxis that intersects the interiors of the objects. In particular, we represent vertices by unit discs and by discs of arbitrary radii (possibly different for different vertices); we also represent vertices by axisaligned unit squares, by axisaligned squares of arbitrary size (possibly different for different vertices), and by axisaligned rectangles. We present: a significant improvement (from 102 to 55) of the best known upper bound for the size of cliques representable by rectangles or squares of arbitrary size; a sharp bound for the representation of cliques by unit squares (K7 can be represented but Kn for n>7 cannot); a representation of Kn by unit discs.
Download: 
Postscript
 Preprinted Version
Download (193kB)  Preview 

Editorial actions:  View Item (Login required) 
Item Type:  Proceedings article 

Citations:  40 (Google Scholar)  4 (Web of Science) 
Uncontrolled Keywords:  3dimensional geometry graph drawing graph representation visibility 
Subjects: 

Divisions:  Mathematical Institute 
Related URLs: 
ZAIK Number:  zpr95207 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  19 Dec 2011 09:46 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/207 