Incremental Orthogonal Graph Drawing in Three Dimensions

We present two algorithms for orthogonal graph drawing in three dimensional space. For graphs of maximum degree six, the 3-D drawing is produced in linear time, has volume at most 4.66n³ and each edge has at most three bends. 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