Analogies between the crossing number and the tangle crossing number

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)₂(is₂)the maximum tangle crossing₂(₂) number of a tanglegram with n leaves, we prove¹ⁿ (1 − o(1)) ≤ γ(n) <¹ⁿ . For an arbitrary tanglegram T,.