Accelerated Bend Minimization

Cornelsen, Sabine and Karrenbauer, Andreas (2012) Accelerated Bend Minimization. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 111-122 (Official URL: http://dx.doi.org/ 10.1007/978-3-642-25878-7_12).

Full text not available from this repository.

Abstract

We present an O(n3/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 O(n7/4 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 O(n3/2 ) time.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_12
Classifications:G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:1246

Repository Staff Only: item control page

References

Biedl, T.C., Kant, G.: A better heuristic for orthogonal graph drawings. Computational Geometry 9(3), 159–180 (1998)

Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM Journal on Computing 31(2), 601–625 (2001)

Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM Journal on Computing 16, 421–444 (1987)

Fö̈ßmeier, U., Kaufmann, M.: Drawing High Degree Graphs with Low Bend Numbers. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 254–266. Springer, Heidelberg (1996)

Klau, G.W., Mutzel, P.: Quasi orthogonal drawing of planar graphs. Technical Report MPI-I-98-1-013, Max-Planck-Institut für Informatik, Saarbrücken, Germany (1998), http://data.mpi-sb.mpg.de/internet/reports.nsf

Tamassia, R., Di Battista, G., Batini, C.: Automatic graph drawing and readability of diagrams. IEEE Transactions on Systems, Man and Cybernetics 18(1), 61–79 (1988)

Bertolazzi, P., Di Battista, G., Didimo, W.: Computing orthogonal drawings with the minimum number of bends. IEEE Transactions on Computers 49(8), 826–840 (2000)

Brandes, U., Cornelsen, S., Fieß, C., Wagner, D.: How to draw the minimum cuts of a planar graph. Computational Geometry: Theory and Applications 29(2), 117–133 (2004)

Lütke-Hüttmann, D.: Knickminimales Zeichnen 4-planarer Clustergraphen. Master’s thesis, Universität des Saarlandes (1999) (Diplomarbeit)

Brandes, U., Wagner, D.: Dynamic Grid Embedding with Few Bends and Changes. In: Chwa, K.-Y., Ibarra, O.H. (eds.) ISAAC 1998. LNCS, vol. 1533, pp. 89–98. Springer, Heidelberg (1998)

Brandes, U., Eiglsperger, M., Kaufmann, M., Wagner, D.: Sketch-Driven Orthogonal Graph Drawing. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol. 2528, pp. 1–11. Springer, Heidelberg (2002)

Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows. Prentice-Hall (1993)

Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Heidelberg (2003)

Karmarkar, N.: A new polynomial-time algorithm for linear programming.Combinatorica 4(4), 373–395 (1984)

Imai, H., Iwano, K.: Efficient Sequential and Parallel Algorithms for Planar Minimum Cost Flow. In: Asano, T., Imai, H., Ibaraki, T., Nishizeki, T. (eds.) SIGAL 1990. LNCS, vol. 450, pp. 21–30. Springer, Heidelberg (1990)

Henzinger, M.R., Klein, P., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences 55, 3–23 (1997); Special Issue on Selected Papers from STOC 1994

Fakcharoenphol, J., Rao, S.: Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci. 72, 868–889 (2006)

Klein, P., Mozes, S., Weimann, O.: Shortest paths in directed planar graphs with negative lengths: a linear-space O(n log2 n)-time algorithm. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, pp. 236–245. SIAM, Philadelphia (2009)

Mozes, S., Wulff-Nilsen, C.: Shortest Paths in Planar Graphs with Real Lengths in O(n log2 n/ log log n) Time. In: de Berg, M., Meyer, U. (eds.) ESA 2010. LNCS, vol. 6347, pp. 206–217. Springer, Heidelberg (2010)

Weihe, K.: Maximum (s,t)-flows in planar networks in O(V log V) time. J. Comput. Syst. Sci. 55, 454–475 (1997)

21. Borradaile, G., Klein, P.: An O(n log n) algorithm for maximum st-flow in a directed planar graph. J. ACM 56, 9:1–9:30 (2009)

Hassin, R.: Maximum flow in (s, t) planar networks. Information Processing Letters 13(3), 107 (1981)

Miller, G.L., Naor, J.: Flow in planar graphs with multiple sources and sinks. SIAM J. Comput. 24, 1002–1017 (1995)

Garg, A., Tamassia, R.: A New Minimum Cost Flow Algorithm with Applications to Graph Drawing. In: North, S.C. (ed.) GD 1996. LNCS, vol. 1190, pp. 201–213. Springer, Heidelberg (1997)

Brandenburg, F.J., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Liotta, G., Mutzel, P.: Selected Open Problems in Graph Drawing. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 515–539. Springer, Heidelberg (2004)

Miller, G.L.: Finding small simple cycle separators for 2-connected planar graphs. Journal of Computer and System Sciences 32(4), 265–279 (1986)

Borradaile, G., Klein, P., Mozes, S., Nussbaum, Y., Wulff-Nilsen, C.: Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time. In: Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011 (to appear, 2011)

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall (1999)

Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press (1962)

Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271 (1959)

Tazari, S., Müller-Hannemann, M.: Shortest paths in linear time on minor-closed graph classes, with an application to steiner tree approximation. Discrete Applied Mathematics 157(4), 673–684 (2009)