Three-Dimensional Graph Drawing

Cohen, Robert F. and Eades, Peter and Lin, Tao and Ruskey, Frank (1995) Three-Dimensional Graph Drawing. In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994 , pp. 1-11(Official URL: http://dx.doi.org/10.1007/3-540-58950-3_351).

Full text not available from this repository.

Abstract

Graph drawing research has been mostly oriented toward two-dimensional drawings. This paper describes an investigation of fundamental aspects of three-dimensional graph drawing. In particular we give three results concerning the space required for three-dimensional drawings. We show how to produce a grid drawing of an arbitrary n-vertex graph with all vertices located at integer grid points, in an n \times 2n \times 2n grid, such 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 drawing in a H \times V integer grid to a three-dimensional drawing with \lceil \sqrt{H} \rceil \times \lceil \sqrt{H} \rceil \times V volume. Using this technique we show, for example, that three-dimensional drawings of binary trees can be computed with volume \lceil \sqrt{n} \rceil \times \lceil \sqrt{n} \rceil \times \lceil log n \rceil. We give an algorithm for producing 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 the xy plane. Finally, we list significant unsolved problems in algorithms for three-dimensional graph drawing.

Item Type: Conference Paper 10.1007/3-540-58950-3_351 M Methods > M.999 OthersG Algorithms and Complexity > G.070 Area / Edge LengthP Styles > P.060 3D http://gdea.informatik.uni-koeln.de/id/eprint/259

Actions (login required)

 View Item