Journal of Graph Algorithms and Applications
|Home||Issues||Aims and Scope||Instructions for Authors|
Special Issue on Selected Papers from the Nineteenth International Symposium on Graph Drawing, GD 2011
Accelerated Bend Minimization
Sabine Cornelsen and Andreas Karrenbauer
Vol. 16, no. 3, pp. 635-650, 2012. Regular paper.
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.
Submitted: October 2011.
Reviewed: February 2012.
Revised: March 2012.
Accepted: April 2012.
Final: April 2012.
Published: September 2012.