ThreeDimensional Graph DrawingCohen, Robert F. and Eades, Peter and Lin, Tao and Ruskey, Frank (1995) ThreeDimensional Graph Drawing. In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994 , pp. 111(Official URL: http://dx.doi.org/10.1007/3540589503_351). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540589503_351
AbstractGraph drawing research has been mostly oriented toward twodimensional drawings. This paper describes an investigation of fundamental aspects of threedimensional graph drawing. In particular we give three results concerning the space required for threedimensional drawings. We show how to produce a grid drawing of an arbitrary nvertex 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 twodimensional drawing in a H \times V integer grid to a threedimensional drawing with \lceil \sqrt{H} \rceil \times \lceil \sqrt{H} \rceil \times V volume. Using this technique we show, for example, that threedimensional 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 threedimensional graph drawing.
Actions (login required)
