A binary tanglegram is a pair of binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example in phylogenetics or software engineering, it is required that the individual trees are drawn crossing-free. A natural optimization problem, denoted tanglegram layout problem, is thus to minimize the number of crossings between inter-tree edges. The tanglegram layout problem is NP-hard and is currently considered both in application domains and theory. In this paper we present an experimental comparison of a recursive algorithm of , our variant of their algorithm, the algorithm hierarchy sort of Holten and van Wijk, and an integer quadratic program that yields optimal solutions.
@cite_5: Two kinds of new methods are developed to obtain effective representations of hierarchies automatically: theoretical and heuristic methods. The methods determine the positions of vertices in two steps. First the order of the vertices in each level is determined to reduce the number of crossings of edges. Then horizontal positions of the vertices are determined to improve further the readability of drawings. The theoretical methods are useful in recognizing the nature of the problem, and the heuristic methods make it possible to enlarge the size of hierarchies with which we can deal. Performance tests of the heuristic methods and several applications are presented.
@cite_10: Systems engineers have recently shown interest in algorithms for drawing directed graphs so that they are easy to understand and remember. Each of the commonly used methods has a step which aims to adjust the drawing to decrease the number of arc crossings. We show that the most popular strategy involves an NP-complete problem regarding the minimization of the number of arcs in crossings in a bipartite graph. The performance of the commonly employed “barycenter” heuristic for this problem is analyzed. An alternative method, the “median” heuristic, is proposed and analyzed. The new method is shown to compare favorably with the old in terms of performance guarantees. As a bonus, we show that the median heuristic performs well with regard to the total length of the arcs in the drawing.
@cite_8: We present algorithms for the two layer straightline crossing minimization problem that are able to compute exact optima. Our computational results lead us to the conclusion that there is no need for heuristics if one layer is xed, even though the problem is NP-hard, and that for the general problem with two variable layers, true optima can be computed for sparse instances in which the smaller layer contains up to 15 nodes. For bigger instances, the iterated barycenter method turns out to be the method of choice among several popular heuristics whose performance we could assess by comparing their results to optimum solutions.
In graph drawing the so-called (2SCM) is an important NP-hard problem that occurs when computing layered graph layouts. Such layouts have been introduced by @cite_5 and are widely used for drawing hierarchical graphs. In 2SCM, vertices of a bipartite graph are to be placed on two parallel lines (called ) such that for each vertex on one line all its adjacent vertices lie on the other line. As in TL the objective is to minimize the number of edge crossings provided that edges are drawn as straight-line segments. In one-sided crossing minimization (1SCM) the order of the vertices on one of the layers is fixed. Even 1SCM is NP-hard @cite_10 . J "unger and Mutzel @cite_8 performed an experimental comparison of exact and heuristic algorithms for both 1SCM and 2SCM. The main findings were that for 1SCM the exact solution can be computed quickly for up to 60 vertices in the free layer, and for 2SCM an iterated barycenter heuristic is the method of choice for instances with more than 15 vertices in each layer.