| Discrete and Computational Geometry manuscript No. (will be inserted by the editor) Three-Dimensional Orthogonal Graph Drawing with Optimal Volume (2007) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract An orthogonal drawing of a graph is an embedding of the graph in the rectangular grid, with vertices represented by axis-aligned boxes, and edges represented by paths in the grid which only possibly intersect at common endpoints. In this paper, we study three-dimensional orthogonal drawings and provide lower bounds for three scenarios: (1) drawings where vertices have bounded aspect ratio, (2) drawings where the surface of vertices is proportional to their degree, and (3) drawings without any such restrictions. Then we show that these lower bounds are asymptotically optimal, by providing constructions that match the lower bounds in all scenarios within an order of magnitude. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||