Rectangle and Box Visibility Graphs in 3D

Fekete, Sandor P. and Meijer, Henk (1999) Rectangle and Box Visibility Graphs in 3D.
Published in: International Journal of Computational Geometry and Applications : : IJCGA Vol. 9 (1). pp. 1-27.

Abstract

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 K8 by unit boxes. There is no representation of K10 by unit boxes. There is a representation of K56, using 6 different box shapes. There is no representation of K184 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.


Actions:
Download: [img] Postscript - Preprinted Version
Download (345kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr96-224
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:45
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/224