Skip to content

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.

Presentation

[pdf ]

Audio

MP3MP3

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.

Back to top ∧