Analogies between the Crossing Number and the Tangle Crossing Number - Anderson, Robin; Bai, Shuliang; Barrera-Cruz, Fidel; Czabarka, Éva; Da Lozzo, Giordano; Hobson, Natalie L. F.; Lin, Jephian C.-H.; Mohr, Austin; Smith, Heather C.; Székely, László A.; Whitlatch, Hays (The Electronic Journal of Combinatorics, 2018)
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 12n2(1-o(1))γ(n)<12n2. For an arbitrary tanglegram T, the tangle crossing number, crt(T), is NP-hard to compute (Fernau et al. 2005). We provide an algorithm which lower bounds crt(T) and runs in O(n^4) time. To demonstrate the strength of the algorithm, simulations on tanglegrams chosen uniformly at random suggest that the tangle crossing number is at least 0.055n^2 with high probabilty, which matches the result that the tangle crossing number is Θ(n^2) with high probability (Czabarka et al. 2017).