Drawing binary tanglegrams: an experimental evaluation

M. Nöllenburg, M. Völker, A. Wolff, D.H.R. Holten

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

11 Citations (Scopus)

Abstract

A tanglegram is a pair of trees whose leaf sets are in oneto-one correspondence; matching leaves are connected by inter-tree edges. In applications such as phylogenetics or hierarchical clustering, 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 even for complete binary trees, for general binary trees the problem is hard to approximate if the Unique Games Conjecture holds. In this paper we present an extensive experimental comparison of a new and several known heuristics for the general binary case. We measure the performance of the heuristics with a simple integer linear program and a new exact branch-and-bound algorithm. The new heuristic returns the first solution that the branch-and-bound algorithm computes (in quadratic time). Surprisingly, in most cases this simple heuristic is at least as good as the best of the other heuristics.
Original languageEnglish
Title of host publicationProceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX'09, New York NY, USA, January 3, 2009)
EditorsI. Finnochi, J. Hershberger
Place of PublicationPhiladelphia PA
PublisherSociety for Industrial and Applied Mathematics (SIAM)
Pages106-119
Publication statusPublished - 2009

Fingerprint Dive into the research topics of 'Drawing binary tanglegrams: an experimental evaluation'. Together they form a unique fingerprint.

  • Cite this

    Nöllenburg, M., Völker, M., Wolff, A., & Holten, D. H. R. (2009). Drawing binary tanglegrams: an experimental evaluation. In I. Finnochi, & J. Hershberger (Eds.), Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX'09, New York NY, USA, January 3, 2009) (pp. 106-119). Society for Industrial and Applied Mathematics (SIAM).