Rectangle and box visibility graphs in 3D
We discuss rectangle and box visibility representations of graphs in 3-dimensional space. In these representations, vertices are represented by axis-aligned disjoint rectangles or boxes, Two vertices are adjacent if and only if their corresponding boxes see each other along a small axis-parallel cylinder. We concentrate on lower and upper bounds for the size of the largest complete graph that can be represented. in particular, we examine these bounds 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 can see each other in the x- Or y-directions, which means that the boxes have to see each other in z-parallel direction. This special case has been considered before; we give further results, dealing with the aspects arising from limits on the number of shapes.
visibility graph representation graph drawing 3-dimensional geometry orthogonal objects