Three-Dimensional Orthogonal Graph Drawing with Optimal Volume
Three-Dimensional Orthogonal Graph Drawing with Optimal Volume
复制标题
最优体积三维正交图绘制
作者：
T. Biedl;Torsten Thiele;David R. Wood
摘要图的正交图是将图嵌入到
矩形网格，顶点由轴对齐框表示，
以及由网格中的路径表示的边，只有可能
在公共端点处相交。在这篇论文中，我们研究
三维正交图，并为
三种场景：
(1)顶点具有有界长宽比的图纸，
(2)顶点的表面与其顶点的表面成比例的图
度，以及
(3)不受任何此类限制的图纸。然后我们展示了这些
通过提供构造，下界是渐近最优的
在所有情况下都与常量内的下界匹配
因素。
AbstractAn 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.