Drawing Binary Tanglegrams: An Experimental Evaluation

Simple item page
dc.creatorNöllenburg, Martin
dc.creatorHolten, Danny
dc.creatorVölker, Markus
dc.creatorWolff, Alexander
dc.date2008-06-05
dc.date.accessioned2026-07-07T13:14:45Z
dc.date.available2026-07-07T13:14:45Z
dc.descriptionA binary tanglegram is a pair <S,T> 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 Buchin et al., our variant of their algorithm, the algorithm hierarchy sort of Holten and van Wijk, and an integer quadratic program that yields optimal solutions.
dc.descriptionsee http://www.siam.org/proceedings/alenex/2009/alx09_011_nollenburgm.pdf
dc.identifierhttps://arxiv.org/abs/0806.0928
dc.identifierhttp://arxiv.org/abs/0806.0928
dc.identifierProceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX'09), pages 106-119. SIAM, April 2009
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/230274
dc.subjectData Structures and Algorithms
dc.subjectComputational Geometry
dc.titleDrawing Binary Tanglegrams: An Experimental Evaluation
dc.typetext

Files

Collections

arXiv