3-DIMENSIONAL GRAPH DRAWING

Graph drawing research has been mostly oriented toward two-dimensional drawings. This paper describes an investigation of fundamental aspect s of three-dimensional graph drawing. In particular we give three resu lts concerning the space required for three-dimensional drawings. We s how how to produce a grid drawing of an arbitrary n-vertex graph with all vertices located at integer grid points, in an n x 2n x 2n grid, s uch that no pair of edges cross. This grid size is optimal to within a constant. We also show how to convert an orthogonal two-dimensional d rawing in an H x V integer grid to a three-dimensional drawing with [r oot H] x [root H] x V volume. Using this technique we show, for exampl e, that three-dimensional drawings of binary trees can be computed wit h volume [root n] x [root n] x [root logn]. We give an algorithm for p roducing drawings of rooted trees in which the z-coordinate of a node represents the depth of the node in the tree; our algorithm minimizes the footprint of the drawing, that is, the size of the projection in t he xy plane. Finally, we list significant unsolved problems in algorit hms for three-dimensional graph drawing.