We discuss rectangle and box visibility representations of graphs in 3-dime
nsional space. In these representations, vertices are represented by axis-a
ligned disjoint rectangles or boxes, Two vertices are adjacent if and only
if their corresponding boxes see each other along a small axis-parallel cyl
inder. We concentrate on lower and upper bounds for the size of the largest
complete graph that can be represented. in particular, we examine these bo
unds under certain restrictions: What can be said if we may only use boxes
of a limited number of shapes? Some of the results presented are as follows
:
There is a representation of K-8 by unit boxes.
There is no representation of K-10 by unit boxes.
There is a representation of K-56, using 6 different box shapes.
There is no representation of K-184 by general boxes.
A special case arises for rectangle visibility graphs, where no two boxes c
an see each other in the x- Or y-directions, which means that the boxes hav
e to see each other in z-parallel direction. This special case has been con
sidered before; we give further results, dealing with the aspects arising f
rom limits on the number of shapes.