A New Approximation Algorithm for Bend Minimization in the Kandinsky Model

Yildiz, Canan and Mutzel, Petra and Barth, Wilhelm (2007) A New Approximation Algorithm for Bend Minimization in the Kandinsky Model. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 343-354 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_33).

Full text not available from this repository.

Abstract

The Kandinsky model has been introduced by Fössmeier and Kaufmann in order to deal with planar orthogonal drawings of planar graphs with maximal vertex degree higher than four [7]. No polynomial-time algorithm is known for computing a (region preserving) bend minimal Kandinsky drawing. In this paper we suggest a new 2-approximation algorithm for this problem. Our extensive computational experiments [13] show that the quality of the computed solutions is better than those of its predecessors [6]. E.g., for all instances in the Rome graph benchmark library [4] it computed the optimal solution, and for randomly generated triangulated graphs with up to 800 vertices, the absolute error was less than 2 on average.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_33
Classifications:G Algorithms and Complexity > G.210 Bends
ID Code:789

Repository Staff Only: item control page

References

AGD User Manual, 1999. http://www.ads.tuwien.ac.at/AGD/

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

Batini, C., Nardelli, E., Tamassia, R.: A Layout Algorithm for Data Flow Diagrams. IEEE Trans. Softw. Eng., SE-12(4), pages 538-546, 1986.

Di Battista, G., Garg, A., Liotta, G., Tamassia, R., Tassinari, E., Vargiu, F.: An Experimental Comparison of Three Graph Drawing Algorithms. Proc. 11th Ann. ACM Symp. Comput. Geom., pages 306-315, 1995.

Bertolazzi, P., Di Battista, G., Didimo, W.: Computing orthogonal drawings with the minimum number of bends. IEEE Trans. Comput., 49(8), pages 826-840, 2000.

Eiglsperger, M.: Automatic Layout of UML Calss Diagrams: A Topology-Shape-Metrics Approach. PhD thesis, Eberhard-Karls-Universität zu Tübingen, 2003.

Fößmeier, U., Kaufmann, M.: Drawing high degree graphs with low bend numbers. In F.J. Brandenburg, editor, Proc. 3rd Int. Symp. on Graph Drawing (GD'95), volume 1027 of LNCS, pages 254-266. Springer, 1996.

Fößmeier, U.: Orthogonale Visualisierungstechnicken für Graphen. PhD thesis, Eberhard-Karls-Universität zu Tübingen, 1997.

Fößmeier, U., Kaufmann, M.: Algorithms and Area Bounds for Nonplanar Orthogonal Drawings. In G. Di Battista, editor, Proc. 5th Int. Symp. on Graph Drawing (GD'97), volume 1353 of LNCS, pages 134-145. Springer, 1997.

Garg, A., Tamassia, R.: A New Minimum Cost Flow Algorithm with Applications to Graph Drawing. In S.C. North, editor, Proc. 4th Int. Symp. on Graph Drawing (GD'96), volume 1190 of LNCS, pages 201-216. Springer, 1997.

ILOG CPLEX 8.1: http://www.ilog.com/products/cplex/

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

Yildiz, C.: Knickminimales Orthogonales Zeichnen Planarer Graphen im Kandinsky Modell. PhD thesis, Vienna University of Technology, 2006.