A New Minimum Cost Flow Algorithm with Applications to Graph Drawing

Garg, Ashim and Tamassia, Roberto (1997) A New Minimum Cost Flow Algorithm with Applications to Graph Drawing. In: Symposium on Graph Drawing, GD '96, September 18-20, 1996 , pp. 201-216(Official URL: http://dx.doi.org/10.1007/3-540-62495-3_49).

Full text not available from this repository.


Let N be a single-source single-sink flow network with n nodes, m arcs, and positive arc costs. We present a pseudo-polinomial algorithm that computes a maximum flow of minimum cost for N in time O( X^(3/4)m* \sqrt{logn}), where X is the cost of the flow. This improves upon previously known methods for networks where the minimum cost of the flow is small. We also show an application of our flow algorithm to a well-known graph drawing problem. Namely, we show how to compute a planar orthogonal drawing with the minimum number of bends for an n-vertex embedded planar graph in time O(n^(7/4)* \sqrt{logn}). This is the firs subquadratic algorithm for bend minimization. The previous best bound for this problem was O(n²logn).

Item Type: Conference Paper
Additional Information: 10.1007/3-540-62495-3_49
Classifications: G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.540 Planar
URI: http://gdea.informatik.uni-koeln.de/id/eprint/113

Actions (login required)

View Item View Item