# PLG

## Seminar

### Untangling tanglegrams

St John, K (New York)
Thursday 20 December 2007, 14:20-14:40

Seminar Room 1, Newton Institute

#### Abstract

Given two phylogenetic trees on the same leaf set, how best can they be displayed? If the trees are presented "sideways" with their roots on the outside and leaves in the middle, we can join the corresponding leaves in the trees by edges. Call this diagram a tanglegram. The crossing number of a tanglegram is the number of leaf-leaf edges that cross. Work by Dwyer and Schreiber 04 (and rediscovered by Valiente and co-workers, WABI 07) show that the tanglegram with optimal crossing number can be found in polynomial time if one tree is fixed. We present several new results for the more general case when both trees can be rearranged to give the tanglegram with the minimal crossing number.

#### Video

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.