Universal 3-Dimensional Visibility Representations for Graphs

Helmut Alt, Michael Godau, Sue Whitesides

Institut für Informatik
Freie Universität Berlin
email: alt@inf.fu-berlin.de, godau@inf.fu-berlin.de
Report B 95-14
November 1995

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-95-14.ps.gz
Universal 3-Dimensional Visibility Representations for Graphs

This paper studies 3-dimensional visibility representations of graphs in which objects in 3-d correspond to vertices and vertical visibilities between these objects correspond to edges. We ask which classes of simple objects are universal, i.e. powerful enough to represent all graphs.

In particular, we show that there is no constant k for which the class of all polygons having k or fewer sides is universal. However, we show by construction that every graph on n vertices can be represented by polygons each having at most 2n sides. The construction can be carried out by an O(n^2) algorithm. We also study the universality of classes of simple objects (translates of a single, not necessarily polygonal object) relative to cliques K_n and similarly relative to complete bipartite graphs K_{n,m}.