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, Berkeley, California, USA , pp. 201-216 (Official URL: http://dx.doi.org/10.1007/3-540-62495-3_49).

Full text not available from this repository.

Abstract

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
ID Code:113

Repository Staff Only: item control page

References

R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs, NJ, 1993.

T. Biedl and G. Kant. A Better Heuristic for Orthogonal Graph Drawings. In Proc. 2nd Ann. European Symposium on Algorithms (ESA '94), LNCS, 855, pages 24-35, Springer-Verlag, 1994.

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Algorithms for drawing graphs: An annotated bibliography. Comput. Geom. Theory Appl., 4: 235-282, 1994.

G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, and F. Vargiu. An experimental comparison of three graph drawing algorithms. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 306-315, 1995.

G. Di Battista, A. Giammarco, G. Santucci,and R. Tamassia. The architecture of diagram server. In Proc. IEEE Workshop on Visual Languages (VL '90), pages 60-65, 1990.

G. Di Battista, G. Liotta, and F. Vargiu. Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs. Proc. Workshop on Algorithms and Data Structures, LNCS, 709, Springer-Verlag, 1993, pages 151-162.

G. Di Battista, G. Liotta, and F. Vargiu. Diagram Server. J. Visual Lang. Comput., 6(3):275-298, 1995. (Special issue on Graph Visualization, edited by I.F. Cruz and P. Eades).

S. Even and G. Garnot. Grid layouts of block diagrams - bounding the number of bends in each connection. In R. Tamassia and I.G. Tollis, editors, Graph Drawing (Proc. GD '94), LNCS, 894, Springer-Verlag, pages 64-75, 1995.

L.R. Ford and D.R. Fulkerson. A primal-dual algorithm for the capacitated hitchcock problem. Naval Research Logistics Quarterly, 4:47-54, 1957.

L.R. Ford and D.R. Fulkerson. Flows in Networks. Princeton University Press, Princeton, NJ, 1962.

U. Fößmeier and M. Kaufmann. On bend-minimum orthogonal upward drawing of directed planar graphs. In R. Tamassia and I.G. Tollis, editors, Graph Drawing (Proc. GD '94), LNCS, 894, Springer-Verlag, pages 52-63, 1995.

A. Garg and R. Tamassia. On the Computational Complexity of Upward and Rectilinear Planarity Testing. Proc. DIMACS Workshop GD '94, LNCS, 894, Springer-Verlag, pages 286-297, 1994.

Goos Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16:4-32, 1996. (Special issue on Graph Drawing, edited by G. Di Battista and R. Tamassia).

Y. Liu, P. Marchioro, R. Petreschi, and B. Simeone. Theoretical results on at most 1-bend embeddability of graphs. Technical report, Dipartimento di Statistica, Univ. di Roma "La Sapienza", 1990.

K. Mehlhorn. Gpraph Algorithms and NP-Completeness, vol. 2 of Data Structures and Algorithms. Springer-Verlag, Heidelberg, West Germany, 1984.

A. Papakostas and I.G. Tollis. Improved Algorithms and Bounds for Orthogonal Drawings. Proc. DIMACS Workshop GD '94, LNCS, 894, Springer-Verlag, pages 40-51, 1995.

D.D. Sleator. An O(nmlogn) Algorithm for Maximum Networkflow. PhD thesis, Dept. Comput. Sci., Stanford Univ., Palo Alto, California, 1980.

J. Storer. On minimal node-cost planar embeddings. Network 14 (1984), pages 181-212.

R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16 (1987), pages 421-444.

R. Tamassia and I.G. Tollis. Planar grid embeddings in linear time. IEEE Trans. Circuits Syst., CAS-36(9):1230-1234, 1989.

R.E. Tarjan. Data Structures and Network Algorithms, volume 44 of CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial Applied Mathematics, 1983.

L. Valiant. University Considerations in VLSI Circuits", IEEE Trans. on Comp., vol. C-30, no 2, (1981), pages 135-140, 1981.