{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T11:24:06Z","timestamp":1742988246234,"version":"3.40.3"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031095733"},{"type":"electronic","value":"9783031095740"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-09574-0_6","type":"book-chapter","created":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T17:36:07Z","timestamp":1656005767000},"page":"77-95","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Non-crossing Shortest Paths in\u00a0Undirected Unweighted Planar 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":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5464-4069","authenticated-orcid":false,"given":"Paolo G.","family":"Franciosa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,6,24]]},"reference":[{"key":"6_CR1","unstructured":"Ausiello, G., Balzotti, L., Franciosa, P.G., Lari, I., Ribichini, A.: A Linear Time Algorithm for Computing Max-Flow Vitality in Undirected Unweighted Planar Graphs, CoRR, abs\/2204.10568 (2022)"},{"key":"6_CR2","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_CR3","doi-asserted-by":"crossref","unstructured":"Baker, Z.K., Gokhale, M.B.: On the acceleration of shortest path calculations in transportation networks. In: IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM 2007, pp. 23\u201334 (2007)","DOI":"10.1109\/FCCM.2007.46"},{"key":"6_CR4","unstructured":"Balzotti, L., Franciosa, P.G.: Computing Lengths of Non-Crossing Shortest Paths in Planar Graphs, CoRR, abs\/2011.04047 (2020)"},{"key":"6_CR5","unstructured":"Balzotti, L., Franciosa, P.G.: Max Flow Vitality of Edges and Vertices in Undirected Planar Graphs, CoRR, abs\/2201.13099 (2022)"},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Bauer, R., Delling, D., Sanders, P., Schieferdecker, D., Schultes, D., Wagner, D.: Combining hierarchical and goal-directed speed-up techniques for Dijkstra\u2019s algorithm. ACM J. Exp. Algorithmics 15 (2010)","DOI":"10.1145\/1671970.1671976"},{"key":"6_CR7","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_CR8","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/s00453-010-9459-0","volume":"62","author":"S Cabello","year":"2012","unstructured":"Cabello, S.: Many distances in planar graphs. Algorithmica 62, 361\u2013381 (2012)","journal-title":"Algorithmica"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Chen, D.Z., Xu, J.: Shortest path queries in planar graphs. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 469\u2013478. ACM (2000)","DOI":"10.1145\/335305.335359"},{"key":"6_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/3-540-62559-3_14","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"HN Djidjev","year":"1997","unstructured":"Djidjev, H.N.: Efficient algorithms for shortest path queries in planar digraphs. In: d\u2019Amore, F., Franciosa, P.G., Marchetti-Spaccamela, A. (eds.) WG 1996. LNCS, vol. 1197, pp. 151\u2013165. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/3-540-62559-3_14"},{"key":"6_CR11","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, pp. 735\u2013744. ACM (2013)","DOI":"10.1145\/2488608.2488702"},{"key":"6_CR12","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, pp. 297\u2013208. SIAM (2011)","DOI":"10.1137\/1.9781611973082.25"},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1016\/j.jcss.2005.05.007","volume":"72","author":"J Fakcharoenphol","year":"2006","unstructured":"Fakcharoenphol, J., Rao, S.: Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci. 72, 868\u2013889 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR14","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"GN Frederickson","year":"1987","unstructured":"Frederickson, G.N.: Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput. 16, 1004\u20131022 (1987)","journal-title":"SIAM J. Comput."},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P., Mozes, S., Weimann, O., Wulff-Nilsen, C.: Better tradeoffs for exact distance oracles in planar graphs. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 515\u2013529. SIAM (2018)","DOI":"10.1137\/1.9781611975031.34"},{"key":"6_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/978-3-540-69507-3_6","volume-title":"SOFSEM 2007: Theory and Practice of Computer Science","author":"AV Goldberg","year":"2007","unstructured":"Goldberg, A.V.: Point-to-point shortest path algorithms with preprocessing. In: van Leeuwen, J., Italiano, G.F., van der Hoek, W., Meinel, C., Sack, H., Pl\u00e1\u0161il, F. (eds.) SOFSEM 2007. LNCS, vol. 4362, pp. 88\u2013102. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-69507-3_6"},{"key":"6_CR17","unstructured":"Gross, J.L., Tucker, T.W.: Topological Graph Theory. Courier Corporation (2001)"},{"key":"6_CR18","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0020-0190(81)90120-4","volume":"13","author":"R Hassin","year":"1981","unstructured":"Hassin, R.: Maximum flow in (s, t) planar networks. Inf. Process. Lett. 13, 107 (1981)","journal-title":"Inf. Process. Lett."},{"key":"6_CR19","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1137\/0214045","volume":"14","author":"R Hassin","year":"1985","unstructured":"Hassin, R., Johnson, D.B.: An O(n $$\\log ^2$$n) algorithm for maximum flow in undirected planar networks. SIAM J. Comput. 14, 612\u2013624 (1985)","journal-title":"SIAM J. Comput."},{"key":"6_CR20","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_CR21","doi-asserted-by":"crossref","unstructured":"Italiano, G.F., Nussbaum, Y., Sankowski, P., Wulff-Nilsen, C.: Improved algorithms for min cut and max flow in undirected planar graphs. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, pp. 313\u2013322. ACM (2011)","DOI":"10.1145\/1993636.1993679"},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"Jing, N., Huang, Y., Rundensteiner, E.A.: Hierarchical optimization of optimal path finding for transportation applications. In: CIKM 1996, Proceedings of the Fifth International Conference on Information and Knowledge Management, pp. 261\u2013268. ACM (1996)","DOI":"10.1145\/238355.238550"},{"key":"6_CR23","unstructured":"Kim, D., Maxemchuk, N.F.: Simple robotic routing in ad hoc networks. In: 13th IEEE International Conference on Network Protocols (ICNP 2005), pp. 159\u2013168. IEEE Computer Society (2005)"},{"key":"6_CR24","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_CR25","doi-asserted-by":"crossref","unstructured":"Kowalik, L., Kurowski, M.: Short path queries in planar graphs in constant time. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pp. 143\u2013148. ACM (2003)","DOI":"10.1145\/780542.780565"},{"key":"6_CR26","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1023\/A:1011425821069","volume":"5","author":"Y Kusakari","year":"2001","unstructured":"Kusakari, Y., Masubuchi, D., Nishizeki, T.: Finding a noncrossing steiner forest in plane graphs under a 2-face condition. J. Comb. Optim. 5, 249\u2013266 (2001)","journal-title":"J. Comb. Optim."},{"key":"6_CR27","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.89.012805","volume":"89","author":"AP Masucci","year":"2014","unstructured":"Masucci, A.P., Stanilov, K., Batty, M.: Exploring the evolution of London\u2019s street network in the information space: a dual approach. Phys. Rev. E 89, 012805 (2014)","journal-title":"Phys. Rev. E"},{"key":"6_CR28","doi-asserted-by":"crossref","unstructured":"Mozes, S., Sommer, C.: Exact distance oracles for planar graphs. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 209\u2013222. SIAM (2012)","DOI":"10.1137\/1.9781611973099.19"},{"key":"6_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"642","DOI":"10.1007\/978-3-642-22300-6_54","volume-title":"Algorithms and Data Structures","author":"Y Nussbaum","year":"2011","unstructured":"Nussbaum, Y.: Improved distance queries in planar graphs. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol. 6844, pp. 642\u2013653. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22300-6_54"},{"key":"6_CR30","doi-asserted-by":"publisher","first-page":"1101","DOI":"10.1016\/j.future.2003.11.001","volume":"20","author":"B Raney","year":"2004","unstructured":"Raney, B., Nagel, K.: Iterative route planning for large-scale modular transportation simulations. Future Gener. Comput. Syst. 20, 1101\u20131118 (2004)","journal-title":"Future Gener. Comput. Syst."},{"key":"6_CR31","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_CR32","unstructured":"Steiger, A.J.: Single-face non-crossing shortest paths in planar graphs. M.S. thesis, University of Illinois at Urbana-Champaign (2017). http:\/\/hdl.handle.net\/2142\/98345"},{"key":"6_CR33","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_CR34","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1142\/S0218195997000259","volume":"7","author":"J Takahashi","year":"1997","unstructured":"Takahashi, J., Suzuki, H., Nishizeki, T.: Shortest non-crossing rectilinear paths in plane regions. Int. J. Comput. Geom. Appl. 7, 419\u2013436 (1997)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"6_CR35","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/BF01294465","volume":"15","author":"D Wagner","year":"1995","unstructured":"Wagner, D., Weihe, K.: A linear-time algorithm for edge-disjoint paths in planar graphs. Combinatorica 15, 135\u2013150 (1995)","journal-title":"Combinatorica"},{"key":"6_CR36","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/S0968-090X(97)00004-1","volume":"5","author":"A Ziliaskopoulos","year":"1997","unstructured":"Ziliaskopoulos, A., Kotzinos, D., Mahmassani, H.S.: Design and implementation of parallel time-dependent least time path algorithms for intelligent transportation systems applications. Transp. Res. Part C: Emerg. Technol. 5, 95\u2013107 (1997)","journal-title":"Transp. Res. Part C: Emerg. Technol."}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-09574-0_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,26]],"date-time":"2022-06-26T23:03:16Z","timestamp":1656284596000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-09574-0_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031095733","9783031095740"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-09574-0_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"24 June 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"St. Petersburg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/logic.pdmi.ras.ru\/csr2022\/","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":"51","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":"21","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":"41% - 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":"7","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)"}}]}}