Geodesic
Analogies between the crossing number and the tangle crossing number
Robin Anderson1 ; Shuliang Bai2 ; Fidel Barrera-Cruz ; Éva Czabarka2 ; Giordano Da Lozzo3 ; Natalie L. F. Hobson4 ; Jephian C.-H. Lin5 ; Austin Mohr6 ; Heather C. Smith7 ; László A. Székely2 ; Hays Whitlatch2
1Saint Louis University
2University of South Carolina
3Roma Tre University
4Sonoma State University
5Iowa State University
6Nebraska Wesleyan University
7Davidson College
The electronic journal of combinatorics, Tome 25 (2018) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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).
DOI : 10.37236/7581
Classification : 05C05, 05C62, 68Q25
Mots-clés : tanglegram, crossing number, planarity, trees

Robin Anderson  1   ; Shuliang Bai  2   ; Fidel Barrera-Cruz    ; Éva Czabarka  2   ; Giordano Da Lozzo  3   ; Natalie L. F. Hobson  4   ; Jephian C.-H. Lin  5   ; Austin Mohr  6   ; Heather C. Smith  7   ; László A. Székely  2   ; Hays Whitlatch  2

1 Saint Louis University
2 University of South Carolina
3 Roma Tre University
4 Sonoma State University
5 Iowa State University
6 Nebraska Wesleyan University
7 Davidson College 
@article{10_37236_7581,
     author = {Robin Anderson and Shuliang Bai and Fidel Barrera-Cruz and \'Eva Czabarka and Giordano Da Lozzo and Natalie L. F. Hobson and Jephian C.-H. Lin and Austin Mohr and Heather C. Smith and L\'aszl\'o A. Sz\'ekely and Hays Whitlatch},
     title = {Analogies between the crossing number and the tangle crossing number},
     journal = {The electronic journal of combinatorics},
     year = {2018},
     volume = {25},
     number = {4},
     doi = {10.37236/7581},
     zbl = {1400.05051},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/7581/}
}
TY  - JOUR
AU  - Robin Anderson
AU  - Shuliang Bai
AU  - Fidel Barrera-Cruz
AU  - Éva Czabarka
AU  - Giordano Da Lozzo
AU  - Natalie L. F. Hobson
AU  - Jephian C.-H. Lin
AU  - Austin Mohr
AU  - Heather C. Smith
AU  - László A. Székely
AU  - Hays Whitlatch
TI  - Analogies between the crossing number and the tangle crossing number
JO  - The electronic journal of combinatorics
PY  - 2018
VL  - 25
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/7581/
DO  - 10.37236/7581
ID  - 10_37236_7581
ER  - 
%0 Journal Article
%A Robin Anderson
%A Shuliang Bai
%A Fidel Barrera-Cruz
%A Éva Czabarka
%A Giordano Da Lozzo
%A Natalie L. F. Hobson
%A Jephian C.-H. Lin
%A Austin Mohr
%A Heather C. Smith
%A László A. Székely
%A Hays Whitlatch
%T Analogies between the crossing number and the tangle crossing number
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/7581/
%R 10.37236/7581
%F 10_37236_7581
Robin Anderson; Shuliang Bai; Fidel Barrera-Cruz; Éva Czabarka; Giordano Da Lozzo; Natalie L. F. Hobson; Jephian C.-H. Lin; Austin Mohr; Heather C. Smith; László A. Székely; Hays Whitlatch. Analogies between the crossing number and the tangle crossing number. The electronic journal of combinatorics, Tome 25 (2018) no. 4. doi: 10.37236/7581

Cité par Sources :