Accelerated Bend Minimization

Cornelsen, Sabine and Karrenbauer, Andreas (2012) Accelerated Bend Minimization. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011 , pp. 111-122(Official URL: http://dx.doi.org/ 10.1007/978-3-642-25878-7_12).

Full text not available from this repository.

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.

Item Type:	Conference Paper
Additional Information:	10.1007/978-3-642-25878-7_12
Classifications:	G Algorithms and Complexity > G.210 Bends P Styles > P.600 Poly-line > P.600.700 Orthogonal
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/1246

Actions (login required)

View Item