Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-96-13

August 1996

Rectangle and Box Visibility Graphs in 3D

Sándor P. Fekete and Henk Meijer

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:

A special case arises for rectangle visibility graphs, where no two boxes can see each other in the x- or ydirections, 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.

If you would like a free copy of this report, please send the number of this report, LSE-CDAM-96-13, together with your name and postal address to:
CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.
Phone: +44(0)-171-955 7732.
Fax: +44(0)-171-955 6877.
Email: info@maths.lse.ac.uk

Introduction to the CDAM Research Report Series.
CDAM Homepage.

Copyright © London School of Economics & Political Science 2005

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html