Details

Autor(en) / Beteiligte

• 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

Titel

Analogies between the Crossing Number and the Tangle Crossing Number

Ist Teil von

• The Electronic journal of combinatorics, 2018-11, Vol.25 (4)

Erscheinungsjahr

2018

Link zum Volltext

Quelle

EZB Electronic Journals Library

Beschreibungen/Notizen

• 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))\le\gamma(n)<\frac{1}{2}\binom{n}{2}$. For an arbitrary tanglegram $T$, the tangle crossing number, $\mathrm{crt}(T)$, is NP-hard to compute (Fernau et al. 2005). We provide an algorithm which lower bounds $\mathrm{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 (Czabarka et al. 2017).