{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T05:44:27Z","timestamp":1777355067095,"version":"3.51.4"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T00:00:00Z","timestamp":1770422400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T00:00:00Z","timestamp":1770422400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"TU Wien"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Tanglegrams are drawings of two rooted binary phylogenetic trees and a matching between their leaf sets. The trees are drawn crossing-free on opposite sides with their leaf sets facing each other on two vertical lines. Instead of minimizing the number of pairwise edge crossings, we consider the problem of minimizing the number of\n                    <jats:italic>block crossings<\/jats:italic>\n                    , that is, two bundles of edges crossing each other locally. With one tree fixed, the leaves of the second tree can be permuted according to its tree structure. We give a complete picture of the algorithmic complexity of minimizing block crossings in one-sided tanglegrams by showing -completeness, 2.25-approximations, and a fixed-parameter algorithm with the parameter being the number of block crossings of the computed tanglegram. We also state results for non-binary trees.\n                  <\/jats:p>","DOI":"10.1007\/s00453-025-01363-3","type":"journal-article","created":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T06:29:46Z","timestamp":1770445786000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Block Crossings in One-Sided Tanglegrams"],"prefix":"10.1007","volume":"88","author":[{"given":"Alexander","family":"Dobler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"N\u00f6llenburg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,7]]},"reference":[{"key":"1363_CR1","doi-asserted-by":"publisher","unstructured":"Alam, M.\u00a0J., Fink, M., Pupyrev, S.: The bundled crossing number. In Yifan Hu and Martin N\u00f6llenburg, editors, Proc. 24th Symposium on Graph Drawing and Network Visualization (GD), volume 9801 of LNCS, pages 399\u2013412. Springer, (2016). https:\/\/doi.org\/10.1007\/978-3-319-50106-2_31","DOI":"10.1007\/978-3-319-50106-2_31"},{"issue":"2","key":"1363_CR2","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1137\/S089548019528280X","volume":"11","author":"V Bafna","year":"1998","unstructured":"Bafna, V., Pevzner, P.A.: Sorting by transpositions. SIAM J. Discret. Math. 11(2), 224\u2013240 (1998). https:\/\/doi.org\/10.1137\/S089548019528280X","journal-title":"SIAM J. Discret. Math."},{"issue":"9","key":"1363_CR3","doi-asserted-by":"publisher","first-page":"1070","DOI":"10.1093\/bioinformatics\/btg030","volume":"19","author":"Z Bar-Joseph","year":"2003","unstructured":"Bar-Joseph, Z., Demaine, E.D., Gifford, D.K., Srebro, N., Hamel, A.M., Jaakkola, T.S.: K-ary clustering with optimal leaf ordering for gene expression data. Bioinform. 19(9), 1070\u20131078 (2003). https:\/\/doi.org\/10.1093\/bioinformatics\/btg030","journal-title":"Bioinform."},{"key":"1363_CR4","doi-asserted-by":"publisher","unstructured":"Baumann, F., Buchheim, C., Liers, F.: Exact bipartite crossing minimization under tree constraints. In Paola Festa, editor, Proc. 9th Symposium on Experimental Algorithms (SEA), volume 6049 of LNCS, pages 118\u2013128. Springer, (2010). https:\/\/doi.org\/10.1007\/978-3-642-13193-6_11","DOI":"10.1007\/978-3-642-13193-6_11"},{"key":"1363_CR5","doi-asserted-by":"publisher","unstructured":"B\u00f6cker, S., H\u00fcffner, F., Tru\u00df, A., Wahlstr\u00f6m, M.: A faster fixed-parameter approach to drawing binary tanglegrams. In Jianer Chen and Fedor\u00a0V. Fomin, editors, Proc. 4th Workshop on Parameterized and Exact Computation (IWPEC), volume 5917 of LNCS, pages 38\u201349. Springer, (2009). https:\/\/doi.org\/10.1007\/978-3-642-11269-0_3","DOI":"10.1007\/978-3-642-11269-0_3"},{"issue":"3","key":"1363_CR6","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335\u2013379 (1976). https:\/\/doi.org\/10.1016\/S0022-0000(76)80045-1","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"1363_CR7","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1016\/j.jda.2006.09.003","volume":"5","author":"U Brandes","year":"2007","unstructured":"Brandes, U.: Optimal leaf ordering of complete binary trees. J. Discrete Algorithms 5(3), 546\u2013552 (2007). https:\/\/doi.org\/10.1016\/j.jda.2006.09.003","journal-title":"J. Discrete Algorithms"},{"issue":"1\u20132","key":"1363_CR8","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/s00453-010-9456-3","volume":"62","author":"K Buchin","year":"2012","unstructured":"Buchin, K., Buchin, M., Byrka, J., N\u00f6llenburg, M., Okamoto, Y., Silveira, R.I., Wolff, A.: Drawing (complete) binary tanglegrams - hardness, approximation, fixed-parameter tractability. Algorithmica 62(1\u20132), 309\u2013332 (2012). https:\/\/doi.org\/10.1007\/s00453-010-9456-3","journal-title":"Algorithmica"},{"issue":"3","key":"1363_CR9","doi-asserted-by":"publisher","first-page":"1148","DOI":"10.1137\/110851390","volume":"26","author":"L Bulteau","year":"2012","unstructured":"Bulteau, L., Fertin, G., Rusu, I.: Sorting by transpositions is difficult. SIAM J. Discret. Math. 26(3), 1148\u20131180 (2012). https:\/\/doi.org\/10.1137\/110851390","journal-title":"SIAM J. Discret. Math."},{"key":"1363_CR10","doi-asserted-by":"publisher","unstructured":"Bulteau, L., Gambette, P., Seminck, O.: Reordering a tree according to an order on its leaves. In Hideo Bannai and Jan Holub, editors, Proc. 33rd Symposium on Combinatorial Pattern Matching (CPM), volume 223 of LIPIcs, pages 24:1\u201324:15, (2022). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2022.24","DOI":"10.4230\/LIPIcs.CPM.2022.24"},{"issue":"3","key":"1363_CR11","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1287\/moor.23.3.613","volume":"23","author":"RE Burkard","year":"1998","unstructured":"Burkard, R.E., Deineko, V.G., Woeginger, G.J.: The travelling salesman and the PQ-tree. Math. Oper. Res. 23(3), 613\u2013623 (1998). https:\/\/doi.org\/10.1287\/moor.23.3.613","journal-title":"Math. Oper. Res."},{"key":"1363_CR12","unstructured":"Christie, D.\u00a0A.: Genome rearrangement problems. PhD thesis, University of Glasgow, (1998). URL: https:\/\/theses.gla.ac.uk\/74685\/"},{"key":"1363_CR13","unstructured":"Dwyer, T., Schreiber, F.: Optimal leaf ordering for two and a half dimensional phylogenetic tree visualisation. In Neville Churcher and Clare Churcher, editors, Australasian Symposium on Information Visualisation (InVis.au), volume\u00a035 of CRPIT, pages 109\u2013115. Australian Computer Society, (2004). URL: http:\/\/crpit.scem.westernsydney.edu.au\/abstracts\/CRPITV35Dwyer.html"},{"issue":"4","key":"1363_CR14","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1109\/TCBB.2006.44","volume":"3","author":"I Elias","year":"2006","unstructured":"Elias, I., Hartman, T.: A 1.375-approximation algorithm for sorting by transpositions. IEEE ACM Trans. Comput. Biol. Bioinform. 3(4), 369\u2013379 (2006). https:\/\/doi.org\/10.1109\/TCBB.2006.44","journal-title":"IEEE ACM Trans. Comput. Biol. Bioinform."},{"issue":"1\u20133","key":"1363_CR15","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/S0012-365X(01)00150-9","volume":"241","author":"H Eriksson","year":"2001","unstructured":"Eriksson, H., Eriksson, K., Karlander, J., Svensson, L.J., W\u00e4stlund, J.: Sorting a bridge hand. Discret. Math. 241(1\u20133), 289\u2013300 (2001). https:\/\/doi.org\/10.1016\/S0012-365X(01)00150-9","journal-title":"Discret. Math."},{"issue":"7","key":"1363_CR16","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1016\/j.jcss.2009.10.014","volume":"76","author":"H Fernau","year":"2010","unstructured":"Fernau, H., Kaufmann, M., Poths, M.: Comparing trees via crossing minimization. J. Comput. Syst. Sci. 76(7), 593\u2013608 (2010). https:\/\/doi.org\/10.1016\/j.jcss.2009.10.014","journal-title":"J. Comput. Syst. Sci."},{"key":"1363_CR17","doi-asserted-by":"publisher","unstructured":"Fink, M., Hershberger, J., Suri, S., Verbeek, K.: Bundled crossings in embedded graphs. In Evangelos Kranakis, Gonzalo Navarro, and Edgar Ch vez, editors, Proc. 12th Symposium on Theoretical Informatics (LATIN), volume 9644 of LNCS, pages 454\u2013468. Springer, (2016). https:\/\/doi.org\/10.1007\/978-3-662-49529-2_34","DOI":"10.1007\/978-3-662-49529-2_34"},{"issue":"1","key":"1363_CR18","doi-asserted-by":"publisher","first-page":"111","DOI":"10.7155\/jgaa.00351","volume":"19","author":"M Fink","year":"2015","unstructured":"Fink, M., Pupyrev, S., Wolff, A.: Ordering metro lines by block crossings. J. Graph Algorithms Appl. 19(1), 111\u2013153 (2015). https:\/\/doi.org\/10.7155\/jgaa.00351","journal-title":"J. Graph Algorithms Appl."},{"key":"1363_CR19","unstructured":"Garey, M.\u00a0R., Johnson, D.\u00a0S.: Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman, (1979)"},{"issue":"2","key":"1363_CR20","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/j.ic.2005.09.002","volume":"204","author":"T Hartman","year":"2006","unstructured":"Hartman, T., Shamir, R.: A simpler and faster 1.5-approximation algorithm for sorting by transpositions. Inf. Comput. 204(2), 275\u2013290 (2006). https:\/\/doi.org\/10.1016\/j.ic.2005.09.002","journal-title":"Inf. Comput."},{"issue":"3","key":"1363_CR21","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1111\/j.1467-8659.2008.01205.x","volume":"27","author":"D Holten","year":"2008","unstructured":"Holten, D., van Wijk, J.J.: Visual comparison of hierarchically organized data. Comput. Graph. Forum 27(3), 759\u2013766 (2008). https:\/\/doi.org\/10.1111\/j.1467-8659.2008.01205.x","journal-title":"Comput. Graph. Forum"},{"key":"1363_CR22","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2020.104584","volume":"275","author":"H Jiang","year":"2020","unstructured":"Jiang, H., Liu, H., Chauve, C., Zhu, B.: Breakpoint distance and PQ-trees. Inf. Comput. 275, 104584 (2020). https:\/\/doi.org\/10.1016\/j.ic.2020.104584","journal-title":"Inf. Comput."},{"issue":"1","key":"1363_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13015-022-00205-z","volume":"17","author":"AG Luiz","year":"2022","unstructured":"Luiz, A.G., Silva, L.A., Kowada, B., Rocco, N.R., Maria, E.M., Walter, T.: A new 1.375-approximation algorithm for sorting by transpositions. Algorithms Mol. Biol. 17(1), 1 (2022). https:\/\/doi.org\/10.1186\/s13015-022-00205-z","journal-title":"Algorithms Mol. Biol."},{"issue":"2","key":"1363_CR24","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1142\/S0129054106003863","volume":"17","author":"M Mahajan","year":"2006","unstructured":"Mahajan, M., Rama, R., Raman, V., Vijaykumar, S.: Approximate block sorting. Int. J. Found. Comput. Sci. 17(2), 337\u2013356 (2006). https:\/\/doi.org\/10.1142\/S0129054106003863","journal-title":"Int. J. Found. Comput. Sci."},{"key":"1363_CR25","doi-asserted-by":"publisher","unstructured":"N\u00f6llenburg, M., V\u00f6lker, M., Wolff, A., Holten, D.: Drawing binary tanglegrams: an experimental evaluation. In Irene Finocchi and John Hershberger, editors, Proc. 11th Workshop on Algorithm Engineering and Experiments (ALENEX), pages 106\u2013119. SIAM, (2009). https:\/\/doi.org\/10.1137\/1.9781611972894.11","DOI":"10.1137\/1.9781611972894.11"},{"key":"1363_CR26","doi-asserted-by":"publisher","unstructured":"N\u00f6llenburg, M.: Crossing layout in non-planar graph drawings. In Seok-Hee Hong and Takeshi Tokuyama, editors, Beyond Planar Graphs, Communications of NII Shonan Meetings, pages 187\u2013209. Springer, (2020). https:\/\/doi.org\/10.1007\/978-981-15-6533-5_11","DOI":"10.1007\/978-981-15-6533-5_11"},{"key":"1363_CR27","unstructured":"Page, R. D.\u00a0M.: Tangled trees: phylogeny, cospeciation, and coevolution. University of Chicago Press, (2003)"},{"issue":"13","key":"1363_CR28","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1093\/BIOINFORMATICS\/BTR210","volume":"27","author":"C Scornavacca","year":"2011","unstructured":"Scornavacca, C., Zickmann, F., Huson, D.H.: Tanglegrams for rooted phylogenetic trees and networks. Bioinform. 27(13), 248\u2013256 (2011). https:\/\/doi.org\/10.1093\/BIOINFORMATICS\/BTR210","journal-title":"Bioinform."},{"issue":"5","key":"1363_CR29","doi-asserted-by":"publisher","first-page":"873","DOI":"10.7155\/jgaa.00443","volume":"21","author":"TC van Dijk","year":"2017","unstructured":"van Dijk, T.C., Fink, M., Fischer, N., Lipp, F., Markfelder, P., Ravsky, A., Suri, S., Wolff, A.: Block crossings in storyline visualizations. J. Graph Algorithms Appl. 21(5), 873\u2013913 (2017). https:\/\/doi.org\/10.7155\/jgaa.00443","journal-title":"J. Graph Algorithms Appl."},{"issue":"4","key":"1363_CR30","doi-asserted-by":"publisher","first-page":"588","DOI":"10.1109\/TCBB.2010.57","volume":"7","author":"B Venkatachalam","year":"2010","unstructured":"Venkatachalam, B., Apple, J., John, K.S., Gusfield, D.: Untangling tanglegrams: comparing trees by their drawings. IEEE ACM Trans. Comput. Biol. Bioinform., 7(4), 588\u2013597 (2010). https:\/\/doi.org\/10.1109\/TCBB.2010.57","journal-title":"IEEE ACM Trans. Comput. Biol. Bioinform.,"},{"key":"1363_CR31","doi-asserted-by":"publisher","unstructured":"Walter, M. E. T., Dias, Z., Meidanis, J.: A new approach for approximating the tranposition distance. In Pablo de\u00a0la Fuente, editor, Proc. 7th Symposium on String Processing and Information Retrieval (SPIRE), pages 199\u2013208. IEEE Computer Society, (2000). https:\/\/doi.org\/10.1109\/SPIRE.2000.878196","DOI":"10.1109\/SPIRE.2000.878196"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01363-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01363-3","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01363-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T05:01:20Z","timestamp":1777352480000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01363-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,7]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["1363"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01363-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,7]]},"assertion":[{"value":"14 May 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 November 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflict of interest with regard to this work.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"20"}}