Three-Dimensional Orthogonal Graph Drawing with Optimal Volume |
| |
| Authors: | Therese Biedl Torsten Thiele David R Wood |
| |
| Affiliation: | (1) School of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada;(2) Institut fur Informatik, Freie Universitat Berlin, Takustrasse 19, 14195 Berlin, Germany;(3) Department of Mathematics and Statistics, and School of Computer Science, McGill University, Montreal, Quebec, H3A 2A7, Canada |
| |
| 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 that 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 the vertices have a bounded aspect ratio,
(2) drawings where the surfaces of vertices are proportional to their
degrees, and
(3) drawings without any such restrictions. Then we show that these
lower bounds are asymptotically optimal, by providing constructions
that in all scenarios match the lower bounds within a constant
factor. |
| |
| Keywords: | Graph drawing Orthogonal Three-dimensional Lower bounds |
| 本文献已被 SpringerLink 等数据库收录！ |
|
