Bend-optimal orthogonal graph drawing in the general position model
Bend-optimal orthogonal graph drawing in the general position model
复制标题
一般位置模型中的弯曲最优正交图绘制
DOI：
10.1016/j.comgeo.2013.03.002
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
P. Valtr
中科院分区：
文献类型：
--
作者：
S. Felsner;M. Kaufmann;P. Valtr
我们考虑正交图纸中的一般位置模型，即没有两个点共享一个坐标。图纸也需要是最小的弯曲，即在k维中，图纸的每个边都有一个平行于每个坐标方向的线段，这些线段在k-1个弯曲处粘合在一起。我们提供了一个精确的描述，承认在一般的位置模型在平面上的正交绘图的图形类。证明的主要工具是图的欧拉定向和离散调和函数。为平面情况开发的工具也可以应用于更高的维度。本文讨论了三维空间中的双弯曲图，证明了K2 k+ 2在k+ 1维空间中允许有k-弯曲图.如果我们允许一个顶点位于无穷远处，我们可以在k+ 1维中画出有k个弯曲的K2 k+ 3.
We consider orthogonal drawings in the general position model, ie, no two points share a coordinate. The drawings are also required to be bend minimal, ie, each edge of a drawing in k dimensions has exactly one segment parallel to each coordinate direction that are glued together at k− 1 bends. We provide a precise description of the class of graphs that admit an orthogonal drawing in the general position model in the plane. The main tools for the proof are Eulerian orientations of graphs and discrete harmonic functions. The tools developed for the planar case can also be applied in higher dimensions. We discuss two-bend drawings in three dimensions and show that K 2 k+ 2 admits a k-bend drawing in k+ 1 dimensions. If we allow that a vertex is placed at infinity, we can draw K 2 k+ 3 with k bends in k+ 1 dimensions.
登录
查看更多内容
节省面积的静态和增量图形绘制
DOI：
--
发表时间：
1997
期刊：
Embedded Systems and Applications
影响因子：
--
作者：
T. Biedl;M. Kaufmann
通讯作者：
M. Kaufmann
交互式正交图绘制：算法和界限
DOI：
--
发表时间：
1997
期刊：
International Symposium Graph Drawing and Network Visualization
影响因子：
--
作者：
Ulrich Fößmeier
通讯作者：
Ulrich Fößmeier
影响因子：
1.1
作者：
T. Biedl;Torsten Thiele;David R. Wood
通讯作者：
David R. Wood
DOI：
--
发表时间：
1997
期刊：
影响因子：
--
作者：
D. Wood
通讯作者：
D. Wood
在矩形网格上绘制图形
影响因子：
1.1
作者：
M. Schäffter
通讯作者：
M. Schäffter