Exact bipartite crossing minimization under tree constraints

Baumann F, Buchheim C, Liers F (2010)

Publication Status: Published

Publication Type: Book chapter / Article in edited volumes

Publication year: 2010

Publisher: Springer

Edited Volumes: Experimental Algorithms

Series: Lecture Notes in Computer Science

City/Town: Berlin, Heidelberg

Book Volume: 6049

Pages Range: 118-128

Event location: Naples

ISBN: 9783642131929

DOI: 10.1007/978-3-642-13193-6_11

Abstract

A tanglegram consists of a pair of (not necessarily binary) trees. Additional edges, called tangles, may connect the leaves of the first with those of the second tree. The task is to draw a tanglegram with a minimum number of tangle crossings while making sure that the trees are drawn crossing-free. This problem has relevant applications in computational biology, e.g., for the comparison of phylogenetic trees. Most existing approaches are only applicable for binary trees. In this work, we show that the problem can be formulated as a quadratic linear ordering problem (QLO) with side constraints. Buchheim et al. (INFORMS J. Computing, to appear) showed that, appropriately reformulated, the QLO polytope is a face of some cut polytope. It turns out that the additional side constraints do not destroy this property. Therefore, any polyhedral approach to max-cut can be used in our context. We present experimental results for drawing random and real-world tanglegrams defined on both binary and general trees. We evaluate linear as well as semidefinite programming techniques. By extensive experiments, we show that our approach is very efficient in practice. © Springer-Verlag Berlin Heidelberg 2010.

Authors with CRIS profile

Frauke Liers-Bergmann Professur für Optimization under Uncertainty & Data Analysis

Involved external institutions

Technische Universität Dortmund DE Germany (DE) Universität zu Köln DE Germany (DE)

How to cite

APA:

Baumann, F., Buchheim, C., & Liers, F. (2010). Exact bipartite crossing minimization under tree constraints. In Paola Festa (Eds.), Experimental Algorithms. (pp. 118-128). Berlin, Heidelberg: Springer.

MLA:

Baumann, Frank, Christoph Buchheim, and Frauke Liers. "Exact bipartite crossing minimization under tree constraints." Experimental Algorithms. Ed. Paola Festa, Berlin, Heidelberg: Springer, 2010. 118-128.

BibTeX: Download