Analogies between the crossing number and the tangle crossing number (Q1627199)

Summary: 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 \(\gamma(n)\) is the maximum tangle crossing number of a tanglegram with \(n\) leaves, we prove \(\frac{1}{2}\binom{n}{2}(1-o(1))\leq\gamma(n)<\frac{1}{2}\binom{n}{2}\). For an arbitrary tanglegram \(T\), the tangle crossing number, \(\text{crt}(T)\), is NP-hard to compute. We provide an algorithm which lower bounds \(\text{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 \(\Theta(n^2)\) with high probability [\textit{É. Czabarka} et al., SIAM J. Discrete Math. 31, No. 3, 1732--1750 (2017; Zbl 1368.05022)].