{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,3]],"date-time":"2025-08-03T04:37:49Z","timestamp":1754195869662,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":37,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819705658"},{"type":"electronic","value":"9789819705665"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-981-97-0566-5_4","type":"book-chapter","created":{"date-parts":[[2024,2,28]],"date-time":"2024-02-28T12:03:28Z","timestamp":1709121808000},"page":"32-46","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Quantum Graph Drawing [Best Student Paper]"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-4538-8198","authenticated-orcid":false,"given":"Susanna","family":"Caroppo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2396-5174","authenticated-orcid":false,"given":"Giordano","family":"Da Lozzo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4224-1550","authenticated-orcid":false,"given":"Giuseppe","family":"Di Battista","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,2,29]]},"reference":[{"key":"4_CR1","unstructured":"Aaronson, S.: Introduction to quantum information science lecture notes, April 2019. https:\/\/www.scottaaronson.com\/qclec.pdf"},{"key":"4_CR2","doi-asserted-by":"publisher","unstructured":"Ahmed, A.R., et al.: Splitting vertices in 2-layer graph drawings. IEEE Comput. Graph. Appl. 43(3), 24\u201335 (2023). https:\/\/doi.org\/10.1109\/MCG.2023.3264244","DOI":"10.1109\/MCG.2023.3264244"},{"key":"4_CR3","doi-asserted-by":"publisher","unstructured":"Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M.: 2-Level quasi-planarity or how caterpillars climb (SPQR-)trees. In: Marx, D. (ed.) SODA 2021, pp. 2779\u20132798. SIAM (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.165","DOI":"10.1137\/1.9781611976465.165"},{"key":"4_CR4","doi-asserted-by":"publisher","unstructured":"Angelini, P., Da Lozzo, G., F\u00f6rster, H., Schneck, T.: 2-Layer k-Planar graphs density, crossing lemma, relationships and pathwidth. Comput. J. (2023). https:\/\/doi.org\/10.1093\/comjnl\/bxad038","DOI":"10.1093\/comjnl\/bxad038"},{"issue":"4","key":"4_CR5","doi-asserted-by":"publisher","first-page":"577","DOI":"10.7155\/jgaa.00479","volume":"22","author":"MJ Bannister","year":"2018","unstructured":"Bannister, M.J., Eppstein, D.: Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth. J. Graph Algorithms Appl. 22(4), 577\u2013606 (2018). https:\/\/doi.org\/10.7155\/jgaa.00479","journal-title":"J. Graph Algorithms Appl."},{"key":"4_CR6","doi-asserted-by":"publisher","unstructured":"Barth, W., Mutzel, P., J\u00fcnger, M.: Simple and efficient bilayer cross counting. J. Graph Algorithms Appl. 8(2), 179\u2013194 (2004). https:\/\/doi.org\/10.7155\/JGAA.00088","DOI":"10.7155\/JGAA.00088"},{"key":"4_CR7","doi-asserted-by":"publisher","unstructured":"Bekos, M.A., Da Lozzo, G., Griesbach, S.M., Gronemann, M., Montecchiani, F., Raftopoulou, C.N.: Book embeddings of k-framed graphs and k-map graphs. Discret. Math. 347(1), 113690 (2024). https:\/\/doi.org\/10.1016\/J.DISC.2023.113690","DOI":"10.1016\/J.DISC.2023.113690"},{"key":"4_CR8","doi-asserted-by":"publisher","unstructured":"Bekos, M.A., Gronemann, M., Raftopoulou, C.N.: Two-page book embeddings of 4-planar graphs. Algorithmica 75(1), 158\u2013185 (2016). https:\/\/doi.org\/10.1007\/S00453-015-0016-8","DOI":"10.1007\/S00453-015-0016-8"},{"key":"4_CR9","doi-asserted-by":"publisher","unstructured":"Bernhart, F., Kainen, P.C.: The book thickness of a graph. J. Comb. Theory, Ser. B 27(3), 320\u2013331 (1979). https:\/\/doi.org\/10.1016\/0095-8956(79)90021-2","DOI":"10.1016\/0095-8956(79)90021-2"},{"key":"4_CR10","doi-asserted-by":"publisher","unstructured":"Binucci, C., et al.: Algorithms and characterizations for 2-layer fan-planarity: from caterpillar to stegosaurus. J. Graph Algorithms Appl. 21(1), 81\u2013102 (2017). https:\/\/doi.org\/10.7155\/JGAA.00398","DOI":"10.7155\/JGAA.00398"},{"key":"4_CR11","doi-asserted-by":"publisher","unstructured":"Binucci, C., Di Giacomo, E., Hossain, M.I., Liotta, G.: 1-page and 2-page drawings with bounded number of crossings per edge. Eur. J. Comb. 68, 24\u201337 (2018). https:\/\/doi.org\/10.1016\/J.EJC.2017.07.009","DOI":"10.1016\/J.EJC.2017.07.009"},{"issue":"1","key":"4_CR12","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1287\/ijoc.1090.0318","volume":"22","author":"C Buchheim","year":"2010","unstructured":"Buchheim, C., Wiegele, A., Zheng, L.: Exact algorithms for the quadratic linear ordering problem. INFORMS J. Comput. 22(1), 168\u2013177 (2010). https:\/\/doi.org\/10.1287\/ijoc.1090.0318","journal-title":"INFORMS J. Comput."},{"key":"4_CR13","doi-asserted-by":"publisher","unstructured":"Caroppo, S., Da Lozzo, G., Di Battista, G.: Quantum graph drawing. CoRR abs\/2307.08371 (2023). https:\/\/doi.org\/10.48550\/arXiv.2307.08371","DOI":"10.48550\/arXiv.2307.08371"},{"key":"4_CR14","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, London (1999)"},{"key":"4_CR15","doi-asserted-by":"publisher","unstructured":"Di Giacomo, E., Didimo, W., Eades, P., Liotta, G.: 2-layer right angle crossing drawings. Algorithmica 68(4), 954\u2013997 (2014). https:\/\/doi.org\/10.1007\/S00453-012-9706-7","DOI":"10.1007\/S00453-012-9706-7"},{"key":"4_CR16","doi-asserted-by":"publisher","unstructured":"Diwan, A.A., Roy, B., Ghosh, S.K.: Two-layer drawings of bipartite graphs. Electron. Notes Discret. Math. 61, 351\u2013357 (2017). https:\/\/doi.org\/10.1016\/J.ENDM.2017.06.059","DOI":"10.1016\/J.ENDM.2017.06.059"},{"issue":"2","key":"4_CR17","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/s00453-007-9151-1","volume":"52","author":"V Dujmovic","year":"2008","unstructured":"Dujmovic, V., et al.: On the parameterized complexity of layered graph drawing. Algorithmica 52(2), 267\u2013292 (2008). https:\/\/doi.org\/10.1007\/s00453-007-9151-1","journal-title":"Algorithmica"},{"key":"4_CR18","unstructured":"Eades, P., McKay, B.D., Wormald, N.C.: On an edge crossing problem. In: 9th Australian Computer Science Conference, ACSC 1986, Proceedings, pp. 327\u2013334 (1986)"},{"key":"4_CR19","doi-asserted-by":"publisher","unstructured":"Eades, P., Whitesides, S.: Drawing graphs in two layers. Theor. Comput. Sci. 131(2), 361\u2013374 (1994). https:\/\/doi.org\/10.1016\/0304-3975(94)90179-1","DOI":"10.1016\/0304-3975(94)90179-1"},{"key":"4_CR20","doi-asserted-by":"publisher","unstructured":"Fukuzawa, S., Goodrich, M.T., Irani, S.: Quantum Tutte embeddings. CoRR abs\/2307.08851 (2023). https:\/\/doi.org\/10.48550\/arXiv.2307.08851","DOI":"10.48550\/arXiv.2307.08851"},{"issue":"3","key":"4_CR21","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1137\/0604033","volume":"4","author":"MR Garey","year":"1983","unstructured":"Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM J. Algebr. Discret. Methods 4(3), 312\u2013316 (1983). https:\/\/doi.org\/10.1137\/0604033","journal-title":"SIAM J. Algebr. Discret. Methods"},{"key":"4_CR22","doi-asserted-by":"publisher","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Miller, G.L. (ed.) STOC 1996, pp. 212\u2013219. ACM (1996). https:\/\/doi.org\/10.1145\/237814.237866","DOI":"10.1145\/237814.237866"},{"key":"4_CR23","doi-asserted-by":"publisher","unstructured":"Harrow, A.W.: Quantum algorithms for systems of linear equations. In: Encyclopedia of Algorithms, pp. 1680\u20131683 (2016). https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_771","DOI":"10.1007\/978-1-4939-2864-4_771"},{"key":"4_CR24","unstructured":"J\u00fcnger, M., et al.: Performance of a quantum annealer for ising ground state computations on chimera graphs. CoRR abs\/1904.11965 (2019)"},{"issue":"1","key":"4_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.7155\/jgaa.00001","volume":"1","author":"M J\u00fcnger","year":"1997","unstructured":"J\u00fcnger, M., Mutzel, P.: 2-layer straightline crossing minimization: performance of exact and heuristic algorithms. J. Graph Algorithms Appl. 1(1), 1\u201325 (1997). https:\/\/doi.org\/10.7155\/jgaa.00001","journal-title":"J. Graph Algorithms Appl."},{"issue":"9","key":"4_CR26","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1016\/j.ipl.2016.04.012","volume":"116","author":"Y Kobayashi","year":"2016","unstructured":"Kobayashi, Y., Tamaki, H.: A faster fixed parameter algorithm for two-layer crossing minimization. Inf. Process. Lett. 116(9), 547\u2013549 (2016). https:\/\/doi.org\/10.1016\/j.ipl.2016.04.012","journal-title":"Inf. Process. Lett."},{"key":"4_CR27","unstructured":"Masuda, S., Kashiwabara, T., Nakajima, K., Fujisawa, T.: On the np-completeness of a computer network layout problem. In: Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS 1987), pp. 292\u2013295 (1987)"},{"key":"4_CR28","doi-asserted-by":"publisher","unstructured":"McGeoch, C.C.: Adiabatic Quantum Computation and Quantum Annealing: Theory and Practice. Synthesis Lectures on Quantum Computing. Morgan & Claypool Publishers (2014). https:\/\/doi.org\/10.2200\/S00585ED1V01Y201407QMC008","DOI":"10.2200\/S00585ED1V01Y201407QMC008"},{"key":"4_CR29","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information, 10th Anniversary edn. Cambridge University Press (2016)"},{"key":"4_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/978-3-540-72792-7_23","volume-title":"Integer Programming and Combinatorial Optimization","author":"F Rendl","year":"2007","unstructured":"Rendl, F., Rinaldi, G., Wiegele, A.: A branch and bound algorithm for max-cut based on combining semidefinite and polyhedral relaxations. In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol. 4513, pp. 295\u2013309. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-72792-7_23"},{"key":"4_CR31","unstructured":"Rieffel, E., Polak, W.: Quantum Computing: A Gentle Introduction, 1st edn. The MIT Press, Cambridge (2011)"},{"key":"4_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/3-540-59071-4_53","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"F Shahrokhi","year":"1995","unstructured":"Shahrokhi, F., S\u00fdkora, O., Sz\u00e9kely, L.A., Vrt\u2019o, I.: Book embeddings and crossing numbers. In: Mayr, E.W., Schmidt, G., Tinhofer, G. (eds.) WG 1994. LNCS, vol. 903, pp. 256\u2013268. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-59071-4_53"},{"key":"4_CR33","doi-asserted-by":"crossref","unstructured":"Tamassia, R. (ed.): Handbook on Graph Drawing and Visualization. Chapman and Hall\/CRC, Boca Raton (2013)","DOI":"10.1201\/b15385"},{"issue":"3","key":"4_CR34","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/s00453-007-0118-z","volume":"48","author":"J Tan","year":"2007","unstructured":"Tan, J., Zhang, L.: The consecutive ones submatrix problem for sparse matrices. Algorithmica 48(3), 287\u2013299 (2007). https:\/\/doi.org\/10.1007\/s00453-007-0118-z","journal-title":"Algorithmica"},{"key":"4_CR35","unstructured":"Wigderson, A.: The complexity of the Hamiltonian circuit problem for maximal planar graphs. Technical report TR-298, Princeton University (1982)"},{"issue":"2","key":"4_CR36","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1137\/0210021","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Edge-deletion problems. SIAM J. Comput. 10(2), 297\u2013309 (1981). https:\/\/doi.org\/10.1137\/0210021","journal-title":"SIAM J. Comput."},{"key":"4_CR37","doi-asserted-by":"publisher","unstructured":"Yannakakis, M.: Embedding planar graphs in four pages. J. Comput. Syst. Sci. 38(1), 36\u201367 (1989). https:\/\/doi.org\/10.1016\/0022-0000(89)90032-9","DOI":"10.1016\/0022-0000(89)90032-9"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-97-0566-5_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T16:07:53Z","timestamp":1709654873000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-97-0566-5_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9789819705658","9789819705665"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-981-97-0566-5_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"29 February 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WALCOM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference and Workshops on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Kanazawa","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Japan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 March 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 March 2024","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":"walcom2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.walcom-conference.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":"80","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":"28","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":"35% - 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","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":"1","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)"}}]}}