Accelerated Bend Minimization
Accelerated Bend Minimization
复制标题
加速弯曲最小化
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Andreas Karrenbauer
中科院分区：
文献类型：
--
作者：
Sabine Cornelsen;Andreas Karrenbauer
我们提出了一个$\mathcal O（n^{3/2}）$算法，用于最小化平面图的正交绘图中的弯曲数。在Graph Drawing 2003上，Garg和Tamassia在1996年给出的$\mathcal O（n^{7/4}\sqrt{\log n}）$的上界是否可以改进一直是一个悬而未决的问题。为了回答这个问题，我们展示了如何解决无容量限制的最小成本流问题的平面双向图有界的成本和面的大小在$\mathcal O（n^{3/2}）$时间。
We present an $\mathcal O( n^{3/2})$ algorithm for minimizing the number of bends in an orthogonal drawing of a plane graph. It has been posed as a long standing open problem at Graph Drawing 2003, whether the bound of $\mathcal O(n^{7/4}\sqrt{\log n})$ shown by Garg and Tamassia in 1996 could be improved. To answer this question, we show how to solve the uncapacitated min-cost flow problem on a planar bidirected graph with bounded costs and face sizes in $\mathcal O(n^{3/2})$ time.