Analogies between the Crossing Number and the Tangle Crossing Number

  • Robin Anderson Saint Louis University
  • Shuliang Bai University of South Carolina
  • Fidel Barrera-Cruz
  • Éva Czabarka University of South Carolina
  • Giordano Da Lozzo Roma Tre University
  • Natalie L. F. Hobson Sonoma State University
  • Jephian C.-H. Lin Iowa State University
  • Austin Mohr Nebraska Wesleyan University
  • Heather C. Smith Davidson College
  • László A. Székely University of South Carolina
  • Hays Whitlatch University of South Carolina
Keywords: Tanglegram, Crossing number, Planarity, Trees

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 $\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).

Published
2018-11-02
Article Number
P4.24