Analogies between the crossing number and the tangle crossing number
- Robin Andersong(Author),
- Shuliang Baif(Author),
- Fidel Barrera-Cruz(Author),
- Éva Czabarkac, f(Author),
- Giordano Da Lozzob(Author),
- Natalie L.F. Hobsonh(Author)
- aDavidson College,
- bRoma Tre University,
- cUniversity of Johannesburg,
- dNebraska-Wesleyan University,
- eIowa State University,
- fUniversity of South Carolina
Open access
Abstract
Tanglegrams are special graphs that consist of a pair of rooted binary trees with the same number of leaves, and a perfect matching between the two leaf-sets. These objects are of use in phylogenetics and are represented with straight-line drawings where the leaves of the two plane binary trees are on two parallel lines and only the matching edges can cross. The tangle crossing number of a tanglegram is the minimum number of crossings over all such drawings and is related to biologically relevant quantities, such as the number of times a parasite switched hosts. Our main results for tanglegrams which parallel known theorems for crossing numbers are as follows. The removal of a single matching edge in a tanglegram with n leaves decreases the tangle crossing number by at most n − 3, and this is sharp. Additionally, if γ(n)2(is2)the maximum tangle crossing2(2) number of a tanglegram with n leaves, we prove1n (1 − o(1)) ≤ γ(n) <1n . For an arbitrary tanglegram T,.