{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T22:50:40Z","timestamp":1743029440077,"version":"3.40.3"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031389054"},{"type":"electronic","value":"9783031389061"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-38906-1_25","type":"book-chapter","created":{"date-parts":[[2023,7,27]],"date-time":"2023-07-27T16:05:14Z","timestamp":1690473914000},"page":"386-400","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Block Crossings in\u00a0One-Sided Tanglegrams"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0712-9726","authenticated-orcid":false,"given":"Alexander","family":"Dobler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0454-3937","authenticated-orcid":false,"given":"Martin","family":"N\u00f6llenburg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,28]]},"reference":[{"key":"25_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/978-3-319-50106-2_31","volume-title":"Graph Drawing and Network Visualization","author":"MJ Alam","year":"2016","unstructured":"Alam, M.J., Fink, M., Pupyrev, S.: The bundled crossing number. In: Hu, Y., N\u00f6llenburg, M. (eds.) GD 2016. LNCS, vol. 9801, pp. 399\u2013412. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-50106-2_31"},{"issue":"2","key":"25_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":"25_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. Bioinformatics 19(9), 1070\u20131078 (2003). https:\/\/doi.org\/10.1093\/bioinformatics\/btg030","journal-title":"Bioinformatics"},{"key":"25_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/978-3-642-13193-6_11","volume-title":"Experimental Algorithms","author":"F Baumann","year":"2010","unstructured":"Baumann, F., Buchheim, C., Liers, F.: Exact bipartite crossing minimization under tree constraints. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 118\u2013128. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13193-6_11"},{"key":"25_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/978-3-642-11269-0_3","volume-title":"Parameterized and Exact Computation","author":"S B\u00f6cker","year":"2009","unstructured":"B\u00f6cker, S., H\u00fcffner, F., Truss, A., Wahlstr\u00f6m, M.: A faster fixed-parameter approach to drawing binary tanglegrams. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 38\u201349. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-11269-0_3"},{"issue":"3","key":"25_CR6","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":"25_CR7","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/s00453-010-9456-3","volume":"62","author":"K Buchin","year":"2012","unstructured":"Buchin, K., et al.: 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":"25_CR8","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":"25_CR9","doi-asserted-by":"publisher","unstructured":"Bulteau, L., Gambette, P., Seminck, O.: Reordering a tree according to an order on its leaves. In: Bannai, H., Holub, J. (eds.) Proceedings of 33rd Symposium on Combinatorial Pattern Matching (CPM). LIPIcs, vol. 223, pp. 24:1\u201324:15 (2022). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2022.24","DOI":"10.4230\/LIPIcs.CPM.2022.24"},{"key":"25_CR10","unstructured":"Christie, D.A.: Genome Rearrangement Problems. Ph.D. thesis, University of Glasgow (1998). https:\/\/theses.gla.ac.uk\/74685\/"},{"issue":"5","key":"25_CR11","doi-asserted-by":"publisher","first-page":"873","DOI":"10.7155\/jgaa.00443","volume":"21","author":"TC van Dijik","year":"2017","unstructured":"van Dijik, T.C., et al.: 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."},{"key":"25_CR12","doi-asserted-by":"publisher","unstructured":"Dobler, A., N\u00f6llenburg, M.: Block crossings in one-sided tanglegrams. CoRR abs\/2305.04682 (2023). https:\/\/doi.org\/10.48550\/arXiv.2305.04682","DOI":"10.48550\/arXiv.2305.04682"},{"key":"25_CR13","unstructured":"Dwyer, T., Schreiber, F.: Optimal leaf ordering for two and a half dimensional phylogenetic tree visualisation. In: Churcher, N., Churcher, C. (eds.) Proceedings of Australasian Symposium on Information Visualisation (InVis.au). CRPIT, vol. 35, pp. 109\u2013115. Australian Computer Society (2004). https:\/\/crpit.scem.westernsydney.edu.au\/abstracts\/CRPITV35Dwyer.html"},{"issue":"4","key":"25_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":"25_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":"25_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":"25_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1007\/978-3-662-49529-2_34","volume-title":"LATIN 2016: Theoretical Informatics","author":"M Fink","year":"2016","unstructured":"Fink, M., Hershberger, J., Suri, S., Verbeek, K.: Bundled crossings in embedded graphs. In: Kranakis, E., Navarro, G., Ch\u00e1vez, E. (eds.) LATIN 2016. LNCS, vol. 9644, pp. 454\u2013468. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49529-2_34"},{"issue":"1","key":"25_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":"25_CR19","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, W. H (1979)"},{"issue":"2","key":"25_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":"25_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"},{"issue":"2","key":"25_CR22","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":"25_CR23","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/978-981-15-6533-5_11","volume-title":"Beyond Planar Graphs","author":"M N\u00f6llenburg","year":"2020","unstructured":"N\u00f6llenburg, M.: Crossing layout in non-planar graph drawings. In: Hong, S.-H., Tokuyama, T. (eds.) Beyond Planar Graphs, pp. 187\u2013209. Springer, Singapore (2020). https:\/\/doi.org\/10.1007\/978-981-15-6533-5_11"},{"key":"25_CR24","doi-asserted-by":"publisher","unstructured":"N\u00f6llenburg, M., V\u00f6lker, M., Wolff, A., Holten, D.: Drawing binary tanglegrams: an experimental evaluation. In: Finocchi, I., Hershberger, J. (eds.) Proceedings of 11th Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 106\u2013119. SIAM (2009). https:\/\/doi.org\/10.1137\/1.9781611972894.11","DOI":"10.1137\/1.9781611972894.11"},{"key":"25_CR25","volume-title":"Tangled Trees: Phylogeny, Cospeciation, and Coevolution","author":"RDM Page","year":"2003","unstructured":"Page, R.D.M.: Tangled Trees: Phylogeny, Cospeciation, and Coevolution. University of Chicago Press, Chicago (2003)"},{"issue":"13","key":"25_CR26","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. Bioinformatics 27(13), 248\u2013256 (2011). https:\/\/doi.org\/10.1093\/bioinformatics\/btr210","journal-title":"Bioinformatics"},{"issue":"1","key":"25_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13015-022-00205-z","volume":"17","author":"LAG Silva","year":"2022","unstructured":"Silva, L.A.G., Kowada, L.A.B., Rocco, N.R., Walter, M.E.M.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":"4","key":"25_CR28","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":"25_CR29","doi-asserted-by":"publisher","unstructured":"Walter, M.E.T., Dias, Z., Meidanis, J.: A new approach for approximating the tranposition distance. In: de la Fuente, P. (ed.) Proceedings of 7th Symposium on String Processing and Information Retrieval (SPIRE), pp. 199\u2013208. IEEE Computer Society (2000). https:\/\/doi.org\/10.1109\/SPIRE.2000.878196","DOI":"10.1109\/SPIRE.2000.878196"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-38906-1_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,27]],"date-time":"2023-07-27T16:08:05Z","timestamp":1690474085000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-38906-1_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031389054","9783031389061"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-38906-1_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"28 July 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Algorithms and Data Structures Symposium","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Montreal, QC","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 July 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 August 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/wads.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"92","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"47","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"51% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}