Name
Abstract | ||
|---|---|---|
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 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 $\mathcal O(n^{3/2})$ time. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-25878-7_12 | J. Graph Algorithms Appl. |
Keywords | DocType | Volume |
planar bidirected graph,open problem,uncapacitated min-cost flow problem,plane graph,graph drawing,face size,mathcal o,bounded cost,log n,long standing | Conference | 16 |
Issue | ISSN | Citations |
3 | 0302-9743 | 3 |
PageRank | References | Authors |
0.41 | 24 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sabine Cornelsen | 1 | 144 | 19.85 |
| Andreas Karrenbauer | 2 | 133 | 20.21 |