The paper in this page has been just accepted in JGAA and is in the queue for being assigned a volume and an issue number. It has been accepted by one of the JGAA editors and its content will no longer be modified. However, the publication format of the paper may still be subject to minor changes.

DOI: 10.7155/jgaa.00265
Accelerated Bend Minimization
Sabine Cornelsen and Andreas Karrenbauer
To be published in the Special Issue of GD 2011.

Abstract 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 flow problem on a planar bidirected graph with bounded costs and face sizes in O( n3/2) time.
Posted here: April 2012.


Journal of Graph Algorithms and Applications