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