1997 | ReviewPaper | Chapter
A new minimum cost flow algorithm with applications to graph drawing
Authors : Ashim Garg, Roberto Tamassia
Published in: Graph Drawing
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Let N be a single-source single-sink flow network with n nodes, m arcs, and positive arc costs. We present a pseudo-polynomial algorithm that computes a maximum flow of minimum cost for N in time O(χ3/4m√log n), where χ 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(n7/4√log n). This is the first subquadratic algorithm for bend minimization. The previous best bound for this problem was O(n2 log n) [19].