Tech Report CS-89-10

Representations of Graphs on a Cylinder

Roberto Tamassia and Ioannis G. Tollis

January 1989

Abstract:

We present a complete characterization of the class of graphs that admit a {\em cylindric visibility representation}, where vertices are represented by intervals parallel to the axis of the cylinder and the edges correspond to visible intervals. Moreover, we give linear-time algorithms for testing the existence of and constructing such a representation. Important applications of cylindric visibility representations can be found in the layout of regular VLSI circuits, such as linear systolic arrays and bit-slice architectures. Also, we present alternative ``dual'' characterizations of the graphs that admit visibility representations in the plane and in the cylinder. It is interesting to observe that neither of these two classes is contained in the other, although they have a nonempty intersection.

(complete text in pdf)