A New Algorithm and Open Problems in Three-Dimensional Orthogonal Graph Drawing
David R. Wood · 1999
. In this paper we present an algorithm for 3-D orthogonal drawing of arbitrary degree n-vertex m-edge multigraphs with O(m 2 = p n) bounding box volume and 6 bends per edge route. This is the smallest known bound on the bounding box volume of 3-D orthogonal multigraph drawings. We continue the study of the tradeoff between bounding box volume and the number of bends in orthogonal graph drawings through a refined algorithm with O(m 2 ) bounding box volume and 5 bends per edge route. Many open problems in 3-D orthogonal graph drawing are presented and potential avenues for their solution are discussed. 1 Introduction With applications including VLSI circuit design [4, 18, 20] and software engineering [14, 19, 23], there has been recent interest in 3-D graph visualization. Proposed models include straight-line drawings [6, 13, 16] and of interest in this paper orthogonal drawings [1, 2, 5, 8, 9, 10, 11, 15, 17, 25, 26, 27, 28]. The 3-D orthogonal grid consists of grid po...