{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:44:17Z","timestamp":1753893857583,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>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)&lt;\\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).<\/jats:p>","DOI":"10.37236\/7581","type":"journal-article","created":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T10:04:28Z","timestamp":1578650668000},"source":"Crossref","is-referenced-by-count":2,"title":["Analogies between the Crossing Number and the Tangle Crossing Number"],"prefix":"10.37236","volume":"25","author":[{"given":"Robin","family":"Anderson","sequence":"first","affiliation":[]},{"given":"Shuliang","family":"Bai","sequence":"additional","affiliation":[]},{"given":"Fidel","family":"Barrera-Cruz","sequence":"additional","affiliation":[]},{"given":"\u00c9va","family":"Czabarka","sequence":"additional","affiliation":[]},{"given":"Giordano","family":"Da Lozzo","sequence":"additional","affiliation":[]},{"given":"Natalie L. F.","family":"Hobson","sequence":"additional","affiliation":[]},{"given":"Jephian C.-H.","family":"Lin","sequence":"additional","affiliation":[]},{"given":"Austin","family":"Mohr","sequence":"additional","affiliation":[]},{"given":"Heather C.","family":"Smith","sequence":"additional","affiliation":[]},{"given":"L\u00e1szl\u00f3 A.","family":"Sz\u00e9kely","sequence":"additional","affiliation":[]},{"given":"Hays","family":"Whitlatch","sequence":"additional","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2018,11,2]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v25i4p24\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v25i4p24\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,16]],"date-time":"2020-01-16T23:21:49Z","timestamp":1579216909000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v25i4p24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,2]]},"references-count":0,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2018,10,5]]}},"URL":"https:\/\/doi.org\/10.37236\/7581","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2018,11,2]]},"article-number":"P4.24"}}