{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T19:39:02Z","timestamp":1743104342259,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031304477"},{"type":"electronic","value":"9783031304484"}],"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-30448-4_6","type":"book-chapter","created":{"date-parts":[[2023,4,24]],"date-time":"2023-04-24T20:29:36Z","timestamp":1682368176000},"page":"67-81","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Non-crossing Shortest Paths Lengths in\u00a0Planar Graphs in\u00a0Linear Time"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6191-9801","authenticated-orcid":false,"given":"Lorenzo","family":"Balzotti","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5464-4069","authenticated-orcid":false,"given":"Paolo G.","family":"Franciosa","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,25]]},"reference":[{"key":"6_CR1","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1002\/net.21878","volume":"74","author":"G Ausiello","year":"2019","unstructured":"Ausiello, G., Franciosa, P.G., Lari, I., Ribichini, A.: Max flow vitality in general and st-planar graphs. Networks 74, 70\u201378 (2019)","journal-title":"Networks"},{"key":"6_CR2","unstructured":"Balzotti, L.: Non-crossing shortest paths are covered with exactly four forests. CoRR (2022)"},{"key":"6_CR3","doi-asserted-by":"publisher","first-page":"589","DOI":"10.7155\/jgaa.00610","volume":"26","author":"L Balzotti","year":"2022","unstructured":"Balzotti, L., Franciosa, P.G.: Non-crossing shortest paths in undirected unweighted planar graphs in linear time. J. Graph Algorithms Appl. 26, 589\u2013606 (2022)","journal-title":"J. Graph Algorithms Appl."},{"key":"6_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-031-09574-0_6","volume-title":"Computer Science - Theory and Applications","author":"L Balzotti","year":"2022","unstructured":"Balzotti, L., Franciosa, P.G.: Non-crossing shortest paths in undirected unweighted planar graphs in linear time. In: Kulikov, A.S., Raskhodnikova, S. (eds.) CSR 2022. LNCS, vol. 13296, pp. 77\u201395. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-09574-0_6"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Balzotti, L., Franciosa, P.G.: How vulnerable is an undirected planar graph with respect to max flow. In: Mavronicolas, M. (ed.) CIAC 2023. LNCS, pp. xx\u2013yy. Springer, Cham (2023)","DOI":"10.1007\/978-3-031-30448-4_7"},{"key":"6_CR6","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","volume":"28","author":"SN Bhatt","year":"1984","unstructured":"Bhatt, S.N., Leighton, F.T.: A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci. 28, 300\u2013343 (1984)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"Das, D., Kipouridis, E., Gutenberg, M.P., Wulff-Nilsen, C.: A simple algorithm for multiple-source shortest paths in planar digraphs. In: 5th Symposium on Simplicity in Algorithms, SOSA, Virtual Conference, pp. 1\u201311. SIAM (2022)","DOI":"10.1137\/1.9781611977066.1"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Eisenstat, D., Klein, P.N.: Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs. In: Symposium on Theory of Computing Conference, STOC 2013, pp. 735\u2013744. ACM (2013)","DOI":"10.1145\/2488608.2488702"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Erickson, J., Nayyeri, A.: Shortest non-crossing walks in the plane. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pp. 297\u2013208. SIAM (2011)","DOI":"10.1137\/1.9781611973082.25"},{"key":"6_CR10","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"HN Gabow","year":"1985","unstructured":"Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30, 209\u2013221 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR11","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"MR Henzinger","year":"1997","unstructured":"Henzinger, M.R., Klein, P.N., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 55, 3\u201323 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR12","unstructured":"Jordan, C.: Cours d\u2019analyse de l\u2019\u00c9cole polytechnique, vol. 1. Gauthier-Villars et fils (1893)"},{"key":"6_CR13","unstructured":"Klein, P.N.: Multiple-source shortest paths in planar graphs. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 146\u2013155. SIAM (2005)"},{"key":"6_CR14","unstructured":"Leighton, F.T.: Complexity Issues in VLSI: Optimal Layouts for the Shuffle-Exchange Graph and Other Networks. MIT Press (1983)"},{"key":"6_CR15","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF01744433","volume":"17","author":"FT Leighton","year":"1984","unstructured":"Leighton, F.T.: New lower bound techniques for VLSI. Math. Syst. Theory 17, 47\u201370 (1984)","journal-title":"Math. Syst. Theory"},{"key":"6_CR16","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1142\/S0218195999000315","volume":"9","author":"E Papadopoulou","year":"1999","unstructured":"Papadopoulou, E.: $$k$$-Pairs non-crossing shortest paths in a simple polygon. Int. J. Comput. Geom. Appl. 9, 533\u2013552 (1999)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"6_CR17","doi-asserted-by":"crossref","unstructured":"Pisanski, T., et al.: Topological graph theory. In: Handbook of Graph Theory, Discrete Mathematics and Its Applications, pp. 610\u2013786. Chapman & Hall\/Taylor & Francis (2003)","DOI":"10.1201\/9780203490204.ch7"},{"key":"6_CR18","doi-asserted-by":"crossref","unstructured":"Polishchuk, V., Mitchell, J.S.B.: Thick non-crossing paths and minimum-cost flows in polygonal domains. In: Proceedings of the 23rd ACM Symposium on Computational Geometry, pp. 56\u201365. ACM (2007)","DOI":"10.1145\/1247069.1247079"},{"key":"6_CR19","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1137\/0212005","volume":"12","author":"JH Reif","year":"1983","unstructured":"Reif, J.H.: Minimum s-t cut of a planar undirected network in $${O}(n\\log ^2(n))$$ time. SIAM J. Comput. 12, 71\u201381 (1983)","journal-title":"SIAM J. Comput."},{"key":"6_CR20","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/BF01955681","volume":"16","author":"J Takahashi","year":"1996","unstructured":"Takahashi, J., Suzuki, H., Nishizeki, T.: Shortest noncrossing paths in plane graphs. Algorithmica 16, 339\u2013357 (1996)","journal-title":"Algorithmica"},{"key":"6_CR21","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P van Emde Boas","year":"1977","unstructured":"van Emde Boas, P.: Preserving order in a forest in less than logarithmic time and linear space. Inf. Process. Lett. 6, 80\u201382 (1977)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-30448-4_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T23:03:38Z","timestamp":1684191818000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-30448-4_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031304477","9783031304484"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-30448-4_6","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":"25 April 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Larnaca","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Cyprus","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":"13 June 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Open","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easy Chair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"49","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":"25","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","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":"6","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":"3 invited papers","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)"}}]}}