Accelerated bend minimization

被引：24

作者：

Cornelsen, Sabine ^{[1
]}

Karrenbauer, Andreas ^{[1
]}

机构：

[1] Department of Computer and Information Science, University of Konstanz, Germany

来源：

Journal of Graph Algorithms and Applications | 2012年 / 16卷 / 03期

关键词：

D O I：

10.7155/jgaa.00265

中图分类号：

TB23 [工程制图];

学科分类号：

摘要：

We present an O(n3/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 O(n7/4√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 ow problem on a planar bidirected graph with bounded costs and face sizes in O(n3/2) time.

引用

页码：635 / 650