# 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.

Download: |
Postscript
- Preprinted Version
Download (345kB) | Preview |
---|---|

Editorial actions: |
View Item (Login required) |

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 |