Rectangle and box visibility graphs in 3D

Citation
Sp. Fekete et H. Meijer, Rectangle and box visibility graphs in 3D, INT J C GEO, 9(1), 1999, pp. 1-27
Citations number
20
Categorie Soggetti
Engineering Mathematics
Journal title
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS
ISSN journal
02181959 → ACNP
Volume
9
Issue
1
Year of publication
1999
Pages
1 - 27
Database
ISI
SICI code
0218-1959(199902)9:1<1:RABVGI>2.0.ZU;2-Z
Abstract
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.