Skip to search boxSkip to navigationSkip to main content

Analogies between the crossing number and the tangle crossing number

  • Robin Anderson
    ,
  • Shuliang Bai
    ,
  • Fidel Barrera-Cruz
    ,
  • Éva Czabarka
    ,
  • Giordano Da Lozzo
    ,
  • Natalie L.F. Hobson
  • Saint Louis University
    ,
  • University of South Carolina
    ,
  • University of Johannesburg
    ,
  • Roma Tre University
    ,
  • Sonoma State University
    ,
  • Iowa State University
Research Output:
Contribution to journal
Article
Peer-review

Open access

Publication metrics

PlumX, opens in new tab

Citations
5
Captures
3

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 γ(n)2(is2)the maximum tangle crossing2(2) number of a tanglegram with n leaves, we prove1n (1 − o(1)) ≤ γ(n) <1n . For an arbitrary tanglegram T,.

Bibliographic Information

Output type

Research Output:
Contribution to journal
Article
Peer-review

Original language

English

Journal (Volume, Issue Number)

Electronic Journal of Combinatorics (Volume 25, Issue 4)

Publication milestones

  • Published - 02/11/2018

Publication status

Published - 02/11/2018

Publication IDs

  • Scopus: 85056251599