The Largest Crossing Number of Tanglegrams
Open Access
- 12 January 2024
- journal article
- research article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 31 (1) , P1.57
Abstract
A tanglegram $\mathcal{T}$ consists of two rooted binary trees with the same number of leaves, and a perfect matching between the two leaf sets. In a layout, the tanglegrams is drawn with the leaves on two parallel lines, the trees on either side of the strip created by these lines are drawn as plane trees, and the perfect matching is drawn in straight line segments inside the strip. The tanglegram crossing number ${\rm cr}({\mathcal{T}})$ of $\mathcal{T}$ is the smallest number of crossings of pairs of matching edges, over all possible layouts of $\mathcal{T}$. The size of the tanglegram is the number of matching edges, say $n$. An earlier paper showed that the maximum of the tanglegram crossing number of size $n$ tanglegrams is $<\frac{1}{2}\binom{n}{2}$; but is at least $\frac{1}{2}\binom{n}{2}-\frac{n^{3/2}-n}{2}$ for infinitely many $n$. Now we make better bounds: the maximum crossing number of a size $n$ tanglegram is at most $\frac{1}{2}\binom{n}{2}-\frac{n}{4}$, but for infinitely many $n$, at least $\frac{1}{2}\binom{n}{2}-\frac{n\log_2 n}{4}$. The problem shows analogy with the Unbalancing Lights Problem of Gale and Berlekamp.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Analogies between the Crossing Number and the Tangle Crossing NumberThe Electronic Journal of Combinatorics, 2018
- Tanglegrams for rooted phylogenetic trees and networksBioinformatics, 2011
- Drawing (Complete) Binary TanglegramsAlgorithmica, 2010
- Untangling Tanglegrams: Comparing Trees by Their Drawings2009
- A Faster Fixed-Parameter Approach to Drawing Binary Tanglegrams2009
- Comparing Trees Via Crossing Minimization2005
- Phylogenetic trees support the coevolution of parasites and their hostsNature, 1988