{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T07:51:10Z","timestamp":1772005870497,"version":"3.50.1"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030044138","type":"print"},{"value":"9783030044145","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"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":[[2018]]},"DOI":"10.1007\/978-3-030-04414-5_34","type":"book-chapter","created":{"date-parts":[[2018,12,17]],"date-time":"2018-12-17T18:20:45Z","timestamp":1545070845000},"page":"481-494","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Bend-Minimum Orthogonal Drawings in Quadratic Time"],"prefix":"10.1007","author":[{"given":"Walter","family":"Didimo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe","family":"Liotta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maurizio","family":"Patrignani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,12,18]]},"reference":[{"issue":"3","key":"34_CR1","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0925-7721(97)00026-6","volume":"9","author":"TC Biedl","year":"1998","unstructured":"Biedl, T.C., Kant, G.: A better heuristic for orthogonal graph drawings. Comput. Geom. 9(3), 159\u2013180 (1998). https:\/\/doi.org\/10.1016\/S0925-7721(97)00026-6","journal-title":"Comput. Geom."},{"issue":"3","key":"34_CR2","doi-asserted-by":"publisher","first-page":"33:1","DOI":"10.1145\/2838736","volume":"12","author":"T Bl\u00e4sius","year":"2016","unstructured":"Bl\u00e4sius, T., Rutter, I., Wagner, D.: Optimal orthogonal graph drawing with convex bend costs. ACM Trans. Algorithms 12(3), 33:1\u201333:32 (2016). https:\/\/doi.org\/10.1145\/2838736","journal-title":"ACM Trans. Algorithms"},{"key":"34_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/978-3-540-24595-7_55","volume-title":"Graph Drawing","author":"F Brandenburg","year":"2004","unstructured":"Brandenburg, F., Eppstein, D., Goodrich, M.T., Kobourov, S., Liotta, G., Mutzel, P.: Selected open problems in graph drawing. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 515\u2013539. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24595-7_55"},{"key":"34_CR4","doi-asserted-by":"publisher","unstructured":"Chang, Y., Yen, H.: On bend-minimized orthogonal drawings of planar 3-graphs. In: Aronov, B., Katz, M.J. (eds.) 33rd International Symposium on Computational Geometry, SoCG 2017, 4\u20137 July 2017, Brisbane, Australia. LIPIcs, vol. 77, pp. 29:1\u201329:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2017.29, http:\/\/www.dagstuhl.de\/dagpub\/978-3-95977-038-5","DOI":"10.4230\/LIPIcs.SoCG.2017.29"},{"key":"34_CR5","doi-asserted-by":"publisher","unstructured":"Cohen, M.B., Madry, A., Tsipras, D., Vladu, A.: Matrix scaling and balancing via box constrained newton\u2019s method and interior point methods. In: Umans, C. (ed.) 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15\u201317, 2017. pp. 902\u2013913. IEEE Computer Society (2017). https:\/\/doi.org\/10.1109\/FOCS.2017.88, http:\/\/ieeexplore.ieee.org\/xpl\/mostRecentIssue.jsp?punumber=8100284","DOI":"10.1109\/FOCS.2017.88"},{"issue":"3","key":"34_CR6","doi-asserted-by":"publisher","first-page":"635","DOI":"10.7155\/jgaa.00265","volume":"16","author":"S Cornelsen","year":"2012","unstructured":"Cornelsen, S., Karrenbauer, A.: Accelerated bend minimization. J. Graph Algorithms Appl. 16(3), 635\u2013650 (2012). https:\/\/doi.org\/10.7155\/jgaa.00265","journal-title":"J. Graph Algorithms Appl."},{"key":"34_CR7","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"G Di Battista","year":"1999","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Englewood Cliffs (1999)"},{"issue":"6","key":"34_CR8","doi-asserted-by":"publisher","first-page":"1764","DOI":"10.1137\/S0097539794262847","volume":"27","author":"Giuseppe Di Battista","year":"1998","unstructured":"Di Battista, G., Liotta, G., Vargiu, F.: Spirality and optimal orthogonal drawings. SIAM J. Comput. 27(6), 1764\u20131811 (1998). https:\/\/doi.org\/10.1137\/S0097539794262847","journal-title":"SIAM Journal on Computing"},{"key":"34_CR9","first-page":"1451","volume-title":"Handbook of Discrete and Computational Geometry","author":"E Di Giacomo","year":"2017","unstructured":"Di Giacomo, E., Liotta, G., Tamassia, R.: Graph drawing. In: Goodman, J., O\u2019Rourke, J., Toth, C. (eds.) Handbook of Discrete and Computational Geometry, 3rd edn, pp. 1451\u20131477. Chapman and Hall\/CRC, Boca Raton (2017)","edition":"3"},{"key":"34_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/978-3-662-45803-7_29","volume-title":"Graph Drawing","author":"W Didimo","year":"2014","unstructured":"Didimo, W., Liotta, G., Patrignani, M.: On the Complexity of HV-rectilinear Planarity Testing. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 343\u2013354. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-45803-7_29"},{"key":"34_CR11","unstructured":"Didimo, W., Liotta, G., Patrignani, M.: Bend-minimum orthogonal drawings inquadratic time. CoRR 1804.05813v3 (2018). http:\/\/arxiv.org\/abs\/1804.05813v3"},{"key":"34_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/3-540-46648-7_4","volume-title":"Graph Drawing","author":"A Garg","year":"1999","unstructured":"Garg, A., Liotta, G.: Almost bend-optimal planar orthogonal drawings of biconnected degree-3 planar graphs in quadratic time. In: Kratochv\u00edyl, J. (ed.) GD 1999. LNCS, vol. 1731, pp. 38\u201348. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-46648-7_4"},{"issue":"2","key":"34_CR13","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1137\/S0097539794277123","volume":"31","author":"A Garg","year":"2001","unstructured":"Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31(2), 601\u2013625 (2001). https:\/\/doi.org\/10.1137\/S0097539794277123","journal-title":"SIAM J. Comput."},{"key":"34_CR14","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/3-540-44541-2_8","volume-title":"Graph Drawing","author":"Carsten Gutwenger","year":"2001","unstructured":"Gutwenger, C., Mutzel, P.: A linear time implementation of SPQR-trees. In:Marks, J. (ed.) Graph Drawing, 8th International Symposium, GD 2000,Colonial Williamsburg, VA, USA, September 20-23, 2000, Proceedings. LectureNotes in Computer Science, vol.\u00a01984, pp. 77\u201390. Springer (2000).https:\/\/doi.org\/10.1007\/3-540-44541-2_8"},{"issue":"3","key":"34_CR15","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0202012","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Dividing a graph into triconnected components. SIAM J. Comput. 2(3), 135\u2013158 (1973). https:\/\/doi.org\/10.1137\/0202012","journal-title":"SIAM J. Comput."},{"issue":"1","key":"34_CR16","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1007\/BF02086606","volume":"16","author":"G. Kant","year":"1996","unstructured":"Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16(1), 4\u201332 (1996). https:\/\/doi.org\/10.1007\/BF02086606","journal-title":"Algorithmica"},{"issue":"1\u20133","key":"34_CR17","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0166-218X(97)00076-0","volume":"81","author":"Y Liu","year":"1998","unstructured":"Liu, Y., Morgana, A., Simeone, B.: A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid. Discrete Appl. Math. 81(1\u20133), 69\u201391 (1998). https:\/\/doi.org\/10.1016\/S0166-218X(97)00076-0","journal-title":"Discrete Appl. Math."},{"key":"34_CR18","first-page":"23","volume":"88-D(1)","author":"MS Rahman","year":"2005","unstructured":"Rahman, M.S., Egi, N., Nishizeki, T.: No-bend orthogonal drawings of subdivisions of planar triconnected cubic graphs. IEICE. Transactions 88-D(1), 23\u201330 (2005)","journal-title":"Transactions"},{"issue":"4","key":"34_CR19","doi-asserted-by":"publisher","first-page":"31","DOI":"10.7155\/jgaa.00017","volume":"3","author":"MS Rahman","year":"1999","unstructured":"Rahman, M.S., Nakano, S., Nishizeki, T.: A linear algorithm for bend-optimal orthogonal drawings of triconnected cubic plane graphs. J. Graph Algorithms Appl. 3(4), 31\u201362 (1999). http:\/\/www.cs.brown.edu\/publications\/jgaa\/accepted\/99\/SaidurNakanoNishizeki99.3.4.pdf","journal-title":"J. Graph Algorithms Appl."},{"key":"34_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/3-540-36379-3_32","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"MS Rahman","year":"2002","unstructured":"Rahman, M.S., Nishizeki, T.: Bend-minimum orthogonal drawings of plane 3-graphs. In: Goos, G., Hartmanis, J., van Leeuwen, J., Ku\u010dera, L. (eds.) WG 2002. LNCS, vol. 2573, pp. 367\u2013378. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-36379-3_32"},{"issue":"4","key":"34_CR21","doi-asserted-by":"publisher","first-page":"335","DOI":"10.7155\/jgaa.00074","volume":"7","author":"MS Rahman","year":"2003","unstructured":"Rahman, M.S., Nishizeki, T., Naznin, M.: Orthogonal drawings of plane graphs without bends. J. Graph Algorithms Appl. 7(4), 335\u2013362 (2003). http:\/\/jgaa.info\/accepted\/2003\/Rahman+2003.7.4.pdf","journal-title":"J. Graph Algorithms Appl."},{"key":"34_CR22","doi-asserted-by":"publisher","unstructured":"Storer, J.A.: The node cost measure for embedding graphs on the planar grid (extended abstract). In: Miller, R.E., Ginsburg, S., Burkhard, W.A., Lipton, R.J. (eds.) Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 28\u201330 April 1980, Los Angeles, California, USA, pp. 201\u2013210. ACM (1980). https:\/\/doi.org\/10.1145\/800141.804667","DOI":"10.1145\/800141.804667"},{"issue":"3","key":"34_CR23","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1137\/0216030","volume":"16","author":"Roberto Tamassia","year":"1987","unstructured":"Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16(3), 421\u2013444 (1987). https:\/\/doi.org\/10.1137\/0216030","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"34_CR24","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0020-0190(91)90059-Q","volume":"39","author":"R Tamassia","year":"1991","unstructured":"Tamassia, R., Tollis, I.G., Vitter, J.S.: Lower bounds for planar orthogonal drawings of graphs. Inf. Process. Lett. 39(1), 35\u201340 (1991). https:\/\/doi.org\/10.1016\/0020-0190(91)90059-Q","journal-title":"Inf. Process. Lett."},{"key":"34_CR25","unstructured":"Thomassen, C.: Plane representations of graphs. In: Bondy, J., Murty, U. (eds.) Progress in Graph Theory, pp. 43\u201369 (1987)"},{"issue":"4","key":"34_CR26","doi-asserted-by":"publisher","first-page":"1570","DOI":"10.1137\/060667621","volume":"22","author":"X Zhou","year":"2008","unstructured":"Zhou, X., Nishizeki, T.: Orthogonal drawings of series-parallel graphs with minimum bends. SIAM J. Discrete Math. 22(4), 1570\u20131604 (2008). https:\/\/doi.org\/10.1137\/060667621","journal-title":"SIAM J. Discrete Math."}],"container-title":["Lecture Notes in Computer Science","Graph Drawing and Network Visualization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-04414-5_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T13:21:36Z","timestamp":1710249696000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-04414-5_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030044138","9783030044145"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-04414-5_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"18 December 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"GD","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Graph Drawing and Network Visualization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Barcelona","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Spain","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 September 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 September 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"gd2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/dccg.upc.edu\/gd2018\/","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":"85","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":"41","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":"48% - 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.25","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":"3.92","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)"}},{"value":"The book also contains 1 full invited paper and 1 contest report","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}