Algorithms for Incremental Orthogonal Graph Drawing in Three Dimensions
Achilleas Papakostas, Ioannis G. Tollis · Journal of Graph Algorithms and Applications · 1999
We present two algorithms for orthogonal graph drawing in three dimensional space. For a graph with n vertices of maximum degree six, the 3-D drawing is produced in linear time, has volume at most 4.63n 3 and has at most three bends per edge. If the degree of the graph is arbitrary, the vertices are represented by solid 3-D boxes whose surface is proportional to their degree. The produced drawing has two bends per edge. Both algorithms guarantee no crossings and can be used under an interactive setting (i.e., vertices arrive and enter the drawing on-line), as well. Communicated by G. Di Battista and P. Mutzel. Submitted: March 1998. Revised: November 1998 and April 1999. Research supported in part by NIST, Advanced Technology Program grant number 70NANB5H1162, and by the Texas Advanced Research Program under Grant No. 009741-040. Papakostas and Tollis, Incremental 3-D Drawing , JGAA, 3(4) 81-115 (1999) 82 1 Introduction Graph drawing addresses the problem of automatically...