Optimal Orthogonal Graph Drawing with Convex Bend Costs
Optimal Orthogonal Graph Drawing with Convex Bend Costs
复制标题
具有凸弯曲成本的最优正交图绘制
DOI：
10.1145/2838736
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Dorothea Wagner
中科院分区：
文献类型：
--
作者：
Thomas Bläsius;Ignaz Rutter;Dorothea Wagner
传统上，正交平面图形的质量由折弯总数或每条边的最大折弯数来量化。然而，这忽略了，在典型的应用中，边缘具有不同的重要性。我们考虑如下定义的问题OptimalFlexDraw。给定一个最大度为4的平面图Gonn个顶点（4-平面图），对每条边都有一个代价函数coste：N 0 → R，定义代价取决于弯曲数，求出一个G的最小代价平面正交图，在此一般性下，最优弯曲图是NP-难的.我们表明，它可以有效地解决，如果（1）每个边缘的成本函数是凸的和（2）在每个边缘上的第一个弯曲不造成任何成本。我们的算法对于双连通图和连通图分别需要O（n，n，Tflow（n）和O（n2，n，Tflow（n））的时间，其中Tflow（n）表示在具有多个源和汇的平面网络中计算最小费用流的时间。我们的结果是第一个多项式时间弯曲优化算法的一般4-平面图优化所有嵌入。以前的工作考虑限制图类和单位成本。
Traditionally, the quality of orthogonal planar drawings is quantified by the total number of bends or the maximum number of bends per edge. However, this neglects that, in typical applications, edges have varying importance. We consider the problem OptimalFlexDrawthat is defined as follows. Given a planar graphGonnvertices with maximum degree 4 (4-planar graph) and for each edgeea cost function coste: N0→ R defining costs depending on the number of bendsehas, compute a planar orthogonal drawing ofGof minimum cost.In this generality OptimalFlexDrawis NP-hard. We show that it can be solved efficiently if (1) the cost function of each edge is convex and (2) the first bend on each edge does not cause any cost. Our algorithm takes timeO(n, ⋅,Tflow(n) andO(n2, ⋅,Tflow(n)) for biconnected and connected graphs, respectively, whereTflow(n) denotes the time to compute a minimum-cost flow in a planar network with multiple sources and sinks. Our result is the first polynomial-time bend-optimization algorithm for general 4-planar graphs optimizing over all embeddings. Previous work considers restricted graph classes and unit costs.
登录
查看更多内容
使用 SPQR 树在线维护三元连接组件
影响因子：
1.1
作者：
G. Battista;R. Tamassia
通讯作者：
R. Tamassia
加速弯曲最小化
DOI：
--
发表时间：
2011
期刊：
J. Graph Algorithms Appl.
影响因子：
--
作者：
Sabine Cornelsen;Andreas Karrenbauer
通讯作者：
Andreas Karrenbauer
正交图绘制的更好启发式
影响因子：
1.8
作者：
T. Biedl;G. Kant
通讯作者：
G. Kant
具有灵活性约束的正交图绘制
影响因子：
1.1
作者：
Thomas Bläsius;M. Krug;Ignaz Rutter;D. Wagner
通讯作者：
D. Wagner
具有不灵活边缘的正交图绘制
DOI：
10.1016/j.comgeo.2016.03.001
发表时间：
2016
期刊：
影响因子：
--
作者：
Thomas Bläsius;Sebastian Lehmann;Ignaz Rutter
通讯作者：
Ignaz Rutter