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 , 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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/789

Actions (login required)

View Item View Item