{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,22]],"date-time":"2025-11-22T10:59:49Z","timestamp":1763809189964},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,11,8]],"date-time":"2012-11-08T00:00:00Z","timestamp":1352332800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,4]]},"DOI":"10.1007\/s00453-012-9706-7","type":"journal-article","created":{"date-parts":[[2012,11,7]],"date-time":"2012-11-07T19:51:40Z","timestamp":1352317900000},"page":"954-997","source":"Crossref","is-referenced-by-count":23,"title":["2-Layer Right Angle Crossing Drawings"],"prefix":"10.1007","volume":"68","author":[{"given":"Emilio","family":"Di Giacomo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Walter","family":"Didimo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Eades","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe","family":"Liotta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,11,8]]},"reference":[{"key":"9706_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-642-18469-7_1","volume-title":"Graph Drawing","author":"E. Ackerman","year":"2011","unstructured":"Ackerman, E., Fulek, R., T\u00f3th, C.: On the size of graphs that admit polyline drawings with few bends and crossing angles. In: Brandes, U., Cornelsen, S. (eds.) Graph Drawing. Lecture Notes in Computer Science, vol. 6502, pp. 1\u201312. Springer, Berlin\/Heidelberg (2011)"},{"key":"9706_CR2","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"R.K. Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, New York (1993)"},{"issue":"1","key":"9706_CR3","doi-asserted-by":"crossref","first-page":"53","DOI":"10.7155\/jgaa.00217","volume":"15","author":"P. Angelini","year":"2011","unstructured":"Angelini, P., Cittadini, L., Di Battista, G., Didimo, W., Frati, F., Kaufmann, M., Symvonis, A.: On the perspective opened by right angle crossing drawings. J. Graph Algorithms Appl. 15(1), 53\u201378 (2011). Special issue on GD\u201909","journal-title":"J. Graph Algorithms Appl."},{"key":"9706_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1007\/978-3-642-18381-2_6","volume-title":"SOFSEM 2011: Theory and Practice of Computer Science","author":"E. Argyriou","year":"2011","unstructured":"Argyriou, E., Bekos, M., Symvonis, A.: The straight-line RAC drawing problem is NP-hard. In: Cern\u00e1, I., Gyim\u00f3thy, T., Hromkovic, J., Jefferey, K., Kr\u00e1lovic, R., Vukolic, M., Wolf, S. (eds.) SOFSEM 2011: Theory and Practice of Computer Science. Lecture Notes in Computer Science, vol. 6543, pp. 74\u201385. Springer, Berlin\/Heidelberg (2011)"},{"issue":"4","key":"9706_CR5","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/j.comgeo.2011.11.008","volume":"45","author":"K. Arikushi","year":"2012","unstructured":"Arikushi, K., Fulek, R., Keszegh, B., Moric, F., T\u00f3th, C.D.: Graphs that admit right angle crossing drawings. Comput. Geom. 45(4), 169\u2013177 (2012)","journal-title":"Comput. Geom."},{"key":"9706_CR6","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. Booth","year":"1976","unstructured":"Booth, K., Lueker, G.: Testing for the consecutive ones property, interval graphs and graph planarity using PQ-trees. J. Comput. Syst. Sci. 13, 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"9706_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1007\/978-3-642-25011-8_13","volume-title":"Combinatorial Algorithms","author":"E. Di Giacomo","year":"2011","unstructured":"Di Giacomo, E., Didimo, W., Eades, P., Liotta, G.: 2-layer right angle crossing drawings. In: Iliopoulos, C., Smyth, W. (eds.) Combinatorial Algorithms. Lecture Notes in Computer Science, vol. 7056, pp. 156\u2013169. Springer, Berlin\/Heidelberg (2011)"},{"key":"9706_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/978-3-642-28076-4_21","volume-title":"WALCOM: Algorithms and Computation","author":"E. Di Giacomo","year":"2012","unstructured":"Di Giacomo, E., Didimo, W., Grilli, L., Liotta, G., Romeo, S.: Heuristics for the maximum 2-layer RAC subgraph problem. In: Rahman, M., Nakano, S.-I. (eds.) WALCOM: Algorithms and Computation. Lecture Notes in Computer Science, vol. 7157, pp. 211\u2013216. Springer, Berlin\/Heidelberg (2012)"},{"issue":"3","key":"9706_CR9","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1007\/s00224-010-9275-6","volume":"49","author":"E. Di Giacomo","year":"2011","unstructured":"Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H.: Area, curve complexity, and crossing resolution of non-planar graph drawings. Theory Comput. Syst. 49(3), 565\u2013575 (2011)","journal-title":"Theory Comput. Syst."},{"key":"9706_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1007\/978-3-642-03367-4_19","volume-title":"Algorithms and Data Structures","author":"W. Didimo","year":"2009","unstructured":"Didimo, W., Eades, P., Liotta, G.: Drawing graphs with right angle crossings. In: Dehne, F., Gavrilova, M., Sack, J.-R., T\u00f3th, C.D. (eds.) Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 5664, pp. 206\u2013217. Springer, Berlin\/Heidelberg (2009)"},{"issue":"16","key":"9706_CR11","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1016\/j.ipl.2010.05.023","volume":"110","author":"W. Didimo","year":"2010","unstructured":"Didimo, W., Eades, P., Liotta, G.: A characterization of complete bipartite RAC graphs. Inf. Process. Lett. 110(16), 687\u2013691 (2010)","journal-title":"Inf. Process. Lett."},{"issue":"39","key":"9706_CR12","doi-asserted-by":"crossref","first-page":"5156","DOI":"10.1016\/j.tcs.2011.05.025","volume":"412","author":"W. Didimo","year":"2011","unstructured":"Didimo, W., Eades, P., Liotta, G.: Drawing graphs with right angle crossings. Theor. Comput. Sci. 412(39), 5156\u20135166 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9706_CR13","volume-title":"Thirty Essays on Geometric Graph Theory","author":"W. Didimo","year":"2012","unstructured":"Didimo, W., Liotta, G.: The crossing angle resolution in graph drawing. In: Thirty Essays on Geometric Graph Theory. Springer, Berlin (2012)"},{"issue":"2","key":"9706_CR14","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/s00453-005-1181-y","volume":"45","author":"V. Dujmovi\u0107","year":"2006","unstructured":"Dujmovi\u0107, V., Fellows, M.R., Hallett, M.T., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F.A., Suderman, M., Whitesides, S., Wood, D.R.: A fixed-parameter approach to 2-layer planarization. Algorithmica 45(2), 159\u2013182 (2006)","journal-title":"Algorithmica"},{"key":"9706_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/cjtcs.2011.004","volume":"2011","author":"V. Dujmovic","year":"2011","unstructured":"Dujmovic, V., Gudmundsson, J., Morin, P., Wolle, T.: Notes on large angle crossing graphs. Chic. J. Theor. Comput. Sci. 2011, 1\u201314 (2011)","journal-title":"Chic. J. Theor. Comput. Sci."},{"issue":"1","key":"9706_CR16","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/s00453-004-1093-2","volume":"40","author":"V. Dujmovi\u0107","year":"2004","unstructured":"Dujmovi\u0107, V., Whitesides, S.: An efficient fixed parameter tractable algorithm for 1-sided crossing minimization. Algorithmica 40(1), 15\u201331 (2004)","journal-title":"Algorithmica"},{"key":"9706_CR17","first-page":"89","volume":"21","author":"P. Eades","year":"1986","unstructured":"Eades, P., Kelly, D.: Heuristics for drawing 2-layered networks. Ars Comb. 21, 89\u201398 (1986)","journal-title":"Ars Comb."},{"key":"9706_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/978-3-642-25878-7_15","volume-title":"Graph Drawing","author":"P. Eades","year":"2012","unstructured":"Eades, P., Liotta, G.: Right angle crossing graphs and 1-planarity. In: van Kreveld, M., Speckmann, B. (eds.) Graph Drawing. Lecture Notes in Computer Science, vol. 7034, pp. 148\u2013153. Springer, Berlin\/Heidelberg (2012)"},{"key":"9706_CR19","first-page":"327","volume-title":"Proc. of 9th Australian Computer Science Conference","author":"P. Eades","year":"1986","unstructured":"Eades, P., McKay, B., Wormald, N.: On an edge crossing problem. In: Proc. of 9th Australian Computer Science Conference, pp. 327\u2013334 (1986)"},{"issue":"2","key":"9706_CR20","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/0304-3975(94)90179-1","volume":"131","author":"P. Eades","year":"1994","unstructured":"Eades, P., Whitesides, S.: Drawing graphs in two layers. Theor. Comput. Sci. 131(2), 361\u2013374 (1994)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9706_CR21","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/BF01187020","volume":"11","author":"P. Eades","year":"1994","unstructured":"Eades, P., Wormald, N.C.: Edge crossings in drawings of bipartite graphs. Algorithmica 11(4), 379\u2013403 (1994)","journal-title":"Algorithmica"},{"key":"9706_CR22","first-page":"203","volume":"1","author":"F. Harary","year":"1972","unstructured":"Harary, F., Schwenk, A.: A new crossing number for bipartite graphs. Util. Math. 1, 203\u2013209 (1972)","journal-title":"Util. Math."},{"key":"9706_CR23","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1109\/APVIS.2007.329282","volume-title":"6th International Asia-Pacific Symposium on Visualization. APVIS \u201907","author":"W. Huang","year":"2007","unstructured":"Huang, W.: Using eye tracking to investigate graph layout effects. In: 6th International Asia-Pacific Symposium on Visualization. APVIS \u201907, pp. 97\u2013100 (2007)"},{"key":"9706_CR24","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1109\/PACIFICVIS.2008.4475457","volume-title":"IEEE Pacific Visualization Symposium, 2008. PacificVIS \u201908","author":"W. Huang","year":"2008","unstructured":"Huang, W., Hong, S.-H., Eades, P.: Effects of crossing angles. In: IEEE Pacific Visualization Symposium, 2008. PacificVIS \u201908, pp. 41\u201346 (2008)"},{"key":"9706_CR25","doi-asserted-by":"crossref","unstructured":"J\u00fcnger, M., Mutzel, P.: 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms. J. Graph Algorithms Appl. 1 (1997)","DOI":"10.7155\/jgaa.00001"},{"issue":"4","key":"9706_CR26","doi-asserted-by":"crossref","first-page":"1065","DOI":"10.1137\/S1052623498334013","volume":"11","author":"P. Mutzel","year":"2001","unstructured":"Mutzel, P.: An alternative method to crossing minimization on hierarchical graphs. SIAM J. Optim. 11(4), 1065\u20131080 (2001)","journal-title":"SIAM J. Optim."},{"key":"9706_CR27","doi-asserted-by":"crossref","DOI":"10.1142\/4902","volume-title":"Graph Drawing and Applications for Software and Knowledge Engineers","author":"K. Sugiyama","year":"2002","unstructured":"Sugiyama, K.: Graph Drawing and Applications for Software and Knowledge Engineers. World Scientific, Singapore (2002)"},{"key":"9706_CR28","unstructured":"Tomii, N., Kambayashi, Y., Yajima, S.: On planarization algorithms of 2-level graphs. Inst. Elect. Common. Eng. Jpn. (1977). Technical Report EC77-38"},{"issue":"2","key":"9706_CR29","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0377-2217(95)00356-8","volume":"90","author":"V. Valls","year":"1996","unstructured":"Valls, V., Mart\u00ed, R., Lino, P.: A branch and bound algorithm for minimizing the number of crossing arcs in bipartite graphs. Eur. J. Oper. Res. 90(2), 303\u2013319 (1996)","journal-title":"Eur. J. Oper. Res."},{"key":"9706_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1007\/978-3-642-18469-7_34","volume-title":"Graph Drawing","author":"M. Kreveld van","year":"2011","unstructured":"van Kreveld, M.: The quality ratio of RAC drawings and planar drawings of planar graphs. In: Brandes, U., Cornelsen, S. (eds.) Graph Drawing. Lecture Notes in Computer Science, vol. 6502, pp. 371\u2013376. Springer, Berlin\/Heidelberg (2011)"},{"key":"9706_CR31","first-page":"109","volume":"2","author":"M.S. Waterman","year":"1981","unstructured":"Waterman, M.S., Griggs, J.R.: Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst. Man Cybern. 2, 109\u2013125 (1981)","journal-title":"IEEE Trans. Syst. Man Cybern."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9706-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9706-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9706-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,5]],"date-time":"2019-07-05T10:30:00Z","timestamp":1562322600000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9706-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,11,8]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,4]]}},"alternative-id":["9706"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9706-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,11,8]]}}}