{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T05:15:31Z","timestamp":1770527731207,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1-2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,2]]},"DOI":"10.1007\/s00453-010-9456-3","type":"journal-article","created":{"date-parts":[[2010,10,14]],"date-time":"2010-10-14T07:34:26Z","timestamp":1287041666000},"page":"309-332","source":"Crossref","is-referenced-by-count":21,"title":["Drawing (Complete) Binary Tanglegrams"],"prefix":"10.1007","volume":"62","author":[{"given":"Kevin","family":"Buchin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maike","family":"Buchin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jaroslaw","family":"Byrka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"N\u00f6llenburg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoshio","family":"Okamoto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rodrigo I.","family":"Silveira","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Wolff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,10,14]]},"reference":[{"key":"9456_CR1","series-title":"Lecture Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1007\/978-3-642-00727-9_13","volume-title":"Proc. 1st Internat. Conf. Bioinformatics Comput. Biol. (BICoB\u201909)","author":"M.S. Bansal","year":"2009","unstructured":"Bansal, M.S., Chang, W.-C., Eulenstein, O., Fern\u00e1ndez-Baca, D.: Generalized binary tanglegrams: algorithms and applications. In: Rajasekaran, S. (ed.) Proc. 1st Internat. Conf. Bioinformatics Comput. Biol. (BICoB\u201909). Lecture Notes Comput. Sci., vol. 5462, pp. 114\u2013125. Springer, Berlin (2009)"},{"key":"9456_CR2","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1007\/978-3-642-13193-6_11","volume-title":"Proc. 9th Internat. Sympos. Experimental Algorithms (SEA\u201910)","author":"F. Baumann","year":"2010","unstructured":"Baumann, F., Buchheim, C., Liers, F.: Exact bipartite crossing minimization under tree constraints. In: Festa, P. (ed.) Proc. 9th Internat. Sympos. Experimental Algorithms (SEA\u201910), vol.\u00a06049, pp. 118\u2013128. Springer, Berlin (2010)"},{"issue":"1","key":"9456_CR3","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1137\/S0097539794279626","volume":"27","author":"P. Bertolazzi","year":"1998","unstructured":"Bertolazzi, P., Di Battista, G., Mannino, C., Tamassia, R.: Optimal upward planarity testing of single-source digraphs. SIAM J. Comput. 27(1), 132\u2013169 (1998)","journal-title":"SIAM J. Comput."},{"key":"9456_CR4","series-title":"Lecture Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1007\/978-3-642-11269-0_3","volume-title":"Proc. 4th Internat. Workshop Parameterized and Exact Comput. (IWPEC\u201909)","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. (eds.) Proc. 4th Internat. Workshop Parameterized and Exact Comput. (IWPEC\u201909). Lecture Notes Comput. Sci., vol. 5917, pp. 38\u201349. Springer, Berlin (2009)"},{"key":"9456_CR5","series-title":"Lecture Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1007\/978-3-642-00219-9_32","volume-title":"Proc. 16th Internat. Symp. Graph Drawing (GD\u201908)","author":"K. Buchin","year":"2009","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. In: Tollis, I.G., Patrignani, M. (eds.) Proc. 16th Internat. Symp. Graph Drawing (GD\u201908). Lecture Notes Comput. Sci., vol. 5417, pp. 324\u2013335. Springer, Berlin (2009)"},{"key":"9456_CR6","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1080\/10556780108805818","volume":"15","author":"S. Burer","year":"2001","unstructured":"Burer, S., Monteiro, R.D.: A projected gradient algorithm for solving the Maxcut SDP relaxation. Optim. Methods Softw. 15, 175\u2013200 (2001)","journal-title":"Optim. Methods Softw."},{"key":"9456_CR7","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"9456_CR8","first-page":"427","volume-title":"Proc. 18th Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA\u201997)","author":"B. DasGupta","year":"1997","unstructured":"DasGupta, B., He, X., Jiang, T., Li, M., Tromp, J., Zhang, L.: On distances between phylogenetic trees. In: Proc. 18th Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA\u201997), pp. 427\u2013436 (1997)"},{"issue":"2","key":"9456_CR9","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/j.jda.2006.12.008","volume":"6","author":"V. Dujmovi\u0107","year":"2008","unstructured":"Dujmovi\u0107, V., Fernau, H., Kaufmann, M.: Fixed parameter algorithms for one-sided crossing minimization revisited. J. Discrete Algorithms 6(2), 313\u2013323 (2008)","journal-title":"J. Discrete Algorithms"},{"key":"9456_CR10","series-title":"CRPIT","first-page":"109","volume-title":"Proc. Australasian Sympos. Inform. Visual. (InVis.au\u201904)","author":"T. Dwyer","year":"2004","unstructured":"Dwyer, T., Schreiber, F.: Optimal leaf ordering for two and a half dimensional phylogenetic tree visualization. In: Churcher, N., Churcher, C. (eds.) Proc. Australasian Sympos. Inform. Visual. (InVis.au\u201904). CRPIT, vol. 35, pp. 109\u2013115. Australian Comput. Soc., Canberra (2004)"},{"key":"9456_CR11","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/BF01187020","volume":"10","author":"P. Eades","year":"1994","unstructured":"Eades, P., Wormald, N.: Edge crossings in drawings of bipartite graphs. Algorithmica 10, 379\u2013403 (1994)","journal-title":"Algorithmica"},{"key":"9456_CR12","series-title":"Lecture Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1007\/11590156_37","volume-title":"Proc. 25th Intern. Conf. Found. Softw. Techn. Theoret. Comput. Sci. (FSTTCS\u201905)","author":"H. Fernau","year":"2005","unstructured":"Fernau, H., Kaufmann, M., Poths, M.: Comparing trees via crossing minimization. In: Ramanujam, R., Sen, S. (eds.) Proc. 25th Intern. Conf. Found. Softw. Techn. Theoret. Comput. Sci. (FSTTCS\u201905). Lecture Notes Comput. Sci., vol. 3821, pp. 457\u2013469. Springer, Berlin (2005)"},{"key":"9456_CR13","first-page":"246","volume-title":"Proc. 15th Annu. ACM Symp. Theory Comput. (STOC\u201983)","author":"H.N. Gabow","year":"1983","unstructured":"Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. In: Proc. 15th Annu. ACM Symp. Theory Comput. (STOC\u201983), pp.\u00a0246\u2013251 (1983)"},{"key":"9456_CR14","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. Freeman, New York (1979)"},{"issue":"6","key":"9456_CR15","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"9456_CR16","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1126\/science.8066445","volume":"265","author":"M.S. Hafner","year":"1994","unstructured":"Hafner, M.S., Sudman, P.D., Villablanca, F.X., Spradling, T.A., Demastes, J.W., Nadler, S.A.: Disparate rates of molecular evolution in cospeciating hosts and parasites. Science 265, 1087\u20131090 (1994)","journal-title":"Science"},{"key":"9456_CR17","first-page":"759","volume-title":"Proc. 10th Eurographics\/IE EE-VGTC Sympos. Visualization (EuroVis\u201908)","author":"D. Holten","year":"2008","unstructured":"Holten, D., van Wijk, J.J.: Visual comparison of hierarchically organized data. In: Proc. 10th Eurographics\/IE EE-VGTC Sympos. Visualization (EuroVis\u201908), pp.\u00a0759\u2013766 (2008)"},{"key":"9456_CR18","first-page":"767","volume-title":"Proc. 34th Annu. ACM Sympos. Theory Comput. (STOC\u201902)","author":"S. Khot","year":"2002","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In Proc. 34th Annu. ACM Sympos. Theory Comput. (STOC\u201902), pp.\u00a0767\u2013775 (2002)"},{"key":"9456_CR19","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1109\/SFCS.2005.74","volume-title":"Proc. 46th Annu. IEEE Sympos. Foundat. Comput. Sci. (FOCS\u201905)","author":"S. Khot","year":"2005","unstructured":"Khot, S., Vishnoi, N.K.: The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l 1. In: Proc. 46th Annu. IEEE Sympos. Foundat. Comput. Sci. (FOCS\u201905), pp. 53\u201362 (2005)"},{"key":"9456_CR20","series-title":"Lecture Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1007\/978-3-540-74126-8_10","volume-title":"Proc. 7th Internat. Workshop Algorithms Bioinformatics (WABI\u201907)","author":"A. Lozano","year":"2007","unstructured":"Lozano, A., Pinter, R.Y., Rokhlenko, O., Valiente, G., Ziv-Ukelson, M.: Seeded tree alignment and planar tanglegram layout. In: Giancarlo, R., Hannenhalli, S. (eds.) Proc. 7th Internat. Workshop Algorithms Bioinformatics (WABI\u201907). Lecture Notes Comput. Sci., vol. 4645, pp. 98\u2013110. Springer, Berlin (2007)"},{"issue":"4","key":"9456_CR21","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1007\/s00454-005-1168-0","volume":"33","author":"H. Nagamochi","year":"2005","unstructured":"Nagamochi, H.: An improved bound on the one-sided minimum crossing number in two-layered drawings. Discrete Comput. Geom. 33(4), 565\u2013591 (2005)","journal-title":"Discrete Comput. Geom."},{"key":"9456_CR22","first-page":"106","volume-title":"Proc. 11th Workshop Algorithm Engineering and Experiments (ALENEX\u201909)","author":"M. N\u00f6llenburg","year":"2009","unstructured":"N\u00f6llenburg, M., V\u00f6lker, M., Wolff, A., Holten, D.: Drawing binary tanglegrams: an experimental evaluation. In: Proc. 11th Workshop Algorithm Engineering and Experiments (ALENEX\u201909), pp.\u00a0106\u2013119. SIAM, Philadelphia (2009)"},{"key":"9456_CR23","volume-title":"Tangled Trees: Phylogeny, Cospeciation, and Coevolution","year":"2002","unstructured":"Page, R.D.M. (ed.): Tangled Trees: Phylogeny, Cospeciation, and Coevolution. University of Chicago Press, Chicago (2002)"},{"key":"9456_CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0020-0190(97)00223-8","volume":"65","author":"V. Raman","year":"1998","unstructured":"Raman, V., Ravikumar, B., Rao, S.S.: A simplified NP-complete MAXSAT problem. Inf. Process. Lett. 65, 1\u20136 (1998)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9456_CR25","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1109\/TSMC.1981.4308636","volume":"11","author":"K. Sugiyama","year":"1981","unstructured":"Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst. Man Cybern. 11(2), 109\u2013125 (1981)","journal-title":"IEEE Trans. Syst. Man Cybern."},{"key":"9456_CR26","doi-asserted-by":"crossref","unstructured":"Venkatachalam, B., Apple, J., John, K.St., Gusfield, D.: Untangling tanglegrams: Comparing trees by their drawings. IEEE\/ACM Trans. Comput. Biol. Bioinf., PrePrints (2010). doi: 10.1109\/TCBB.2010.57","DOI":"10.1109\/TCBB.2010.57"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/s00453-010-9456-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T13:02:17Z","timestamp":1559739737000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9456-3"}},"subtitle":["Hardness, Approximation, Fixed-Parameter Tractability"],"short-title":[],"issued":{"date-parts":[[2010,10,14]]},"references-count":26,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["9456"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9456-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10,14]]}}}