Drawing Binary Tanglegrams: An Experimental Evaluation

Details Drawing Binary Tanglegrams: An Experimental Evaluation Drawing Binary Tanglegrams: An Experimental Evaluation

2008-06-05

arxiv.org/abs/0806.0928v1

Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX'09), pages 106-119. SIAM, April 2009

Computer Science

Data Structures and Algorithms

see http://www.siam.org/proceedings/alenex/2009/alx09_011_nollenburgm.pdf

Scientific paper

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 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.

Affiliated with

Also associated with

No associations

Rating

Drawing Binary Tanglegrams: An Experimental Evaluation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Drawing Binary Tanglegrams: An Experimental Evaluation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Drawing Binary Tanglegrams: An Experimental Evaluation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-127862