Accelerated bend minimization. (English) Zbl 1254.05123
Summary: 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 A. Garg and R. Tamassia in 1996 [“A new minimum cost flow algorithm with applications
to graph drawing”, Lect. Notes Comput. Sci., 1190, 20–213 (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.
MSC:
05C62 | Graph representations (geometric and intersection representations, etc.) |
05C10 | Planar graphs; geometric and topological aspects of graph theory |
05C85 | Graph algorithms (graph-theoretic aspects) |