{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T13:38:01Z","timestamp":1772372281003,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2010,10,15]],"date-time":"2010-10-15T00:00:00Z","timestamp":1287100800000},"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":[[2012,2]]},"DOI":"10.1007\/s00453-010-9459-0","type":"journal-article","created":{"date-parts":[[2010,10,14]],"date-time":"2010-10-14T07:48:16Z","timestamp":1287042496000},"page":"361-381","source":"Crossref","is-referenced-by-count":17,"title":["Many Distances in Planar Graphs"],"prefix":"10.1007","volume":"62","author":[{"given":"Sergio","family":"Cabello","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,10,15]]},"reference":[{"key":"9459_CR1","series-title":"LNCS","first-page":"514","volume-title":"ESA\u201996","author":"S. Arikati","year":"1996","unstructured":"Arikati, S., Chen, D.Z., Chew, L.P., Das, G., Smid, M., Zaroliagis, C.: Planar spanners and approximate shortest path queries among obstacles in the plane. In: ESA\u201996. LNCS, vol. 1136, pp. 514\u2013528. Springer, Berlin (1996)"},{"key":"9459_CR2","doi-asserted-by":"crossref","first-page":"1213","DOI":"10.1145\/1109557.1109691","volume-title":"SODA \u201906: Proc. 17th Symp. Discrete Algorithms","author":"S. Cabello","year":"2006","unstructured":"Cabello, S.: Many distances in planar graphs. In: SODA \u201906: Proc. 17th Symp. Discrete Algorithms, pp. 1213\u20131220. ACM Press, New York (2006)"},{"key":"9459_CR3","first-page":"89","volume-title":"SODA \u201907: Proc. 18th Symp. Discrete Algorithms","author":"S. Cabello","year":"2007","unstructured":"Cabello, S., Chambers, E.W.: Multiple source shortest paths in a genus g graph. In: SODA \u201907: Proc. 18th Symp. Discrete Algorithms, pp.\u00a089\u201397 (2007)"},{"issue":"2","key":"9459_CR4","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1007\/s00453-007-9062-1","volume":"50","author":"T.M. Chan","year":"2008","unstructured":"Chan, T.M.: All-pairs shortest paths with real weights in O(n 3\/log\u2009n) time. Algorithmica 50(2), 236\u2013243 (2008)","journal-title":"Algorithmica"},{"key":"9459_CR5","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1145\/335305.335359","volume-title":"STOC \u201900: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing","author":"D.Z. Chen","year":"2000","unstructured":"Chen, D.Z., Xu, J.: Shortest path queries in planar graphs. In: STOC \u201900: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pp.\u00a0469\u2013478 (2000)"},{"key":"9459_CR6","series-title":"LNCS","first-page":"151","volume-title":"WG\u201996","author":"H.N. Djidjev","year":"1997","unstructured":"Djidjev, H.N.: Efficient algorithms for shortest path problems on planar digraphs. In: d\u2019Amore, F., Franciosa, P.G., Marchetti-Spaccamela, A. (eds.) WG\u201996. LNCS, vol. 1197, pp. 151\u2013165. Springer, Berlin (1997)"},{"key":"9459_CR7","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/B978-044482537-7\/50010-3","volume-title":"Handbook of Computational Geometry","author":"D. Eppstein","year":"2000","unstructured":"Eppstein, D.: Spanning trees and spanners. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 425\u2013461. Elsevier, Amsterdam (2000). Chap.\u00a09"},{"issue":"5","key":"9459_CR8","doi-asserted-by":"crossref","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(5), 868\u2013889 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"9459_CR9","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"G.N. 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."},{"issue":"1","key":"9459_CR10","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1145\/102782.102788","volume":"38","author":"G.N. Frederickson","year":"1991","unstructured":"Frederickson, G.N.: Planar graph decomposition and all pairs shortest paths. J. ACM 38(1), 162\u2013204 (1991)","journal-title":"J. ACM"},{"issue":"3","key":"9459_CR11","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1006\/jcss.1995.1076","volume":"51","author":"M.T. Goodrich","year":"1995","unstructured":"Goodrich, M.T.: Planar separators and parallel polygon triangulation. J. Comput. Syst. Sci. 51(3), 374\u2013389 (1995)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9459_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1328911.1328921","volume":"4","author":"J. Gudmundsson","year":"2008","unstructured":"Gudmundsson, J., Levcopoulos, C., Narasimhan, G., Smid, M.: Approximate distance oracles for geometric spanners. ACM Trans. Algorithms 4(1), 1\u201334 (2008)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"9459_CR13","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"M.R. 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(1), 3\u201323 (1997)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9459_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1721837.1721846","volume":"6","author":"P. Klein","year":"2010","unstructured":"Klein, P., Mozes, S., Weimann, O.: Shortest paths in directed planar graphs with negative lengths: A\u00a0linear-space O(nlog\u20092 n)-time algorithm. ACM Trans. Algorithms 6(2), 1\u201318 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"9459_CR15","first-page":"146","volume-title":"SODA \u201905: Proc. 16th Symp. Discrete Algorithms","author":"P.N. Klein","year":"2005","unstructured":"Klein, P.N.: Multiple-source shortest paths in planar graphs. In: SODA \u201905: Proc. 16th Symp. Discrete Algorithms, pp.\u00a0146\u2013155 (2005)"},{"key":"9459_CR16","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1145\/780542.780565","volume-title":"STOC \u201903: Proc. 35th Symp. Theory of Computing","author":"L. Kowalik","year":"2003","unstructured":"Kowalik, L., Kurowski, M.: Short path queries in planar graphs in constant time. In: STOC \u201903: Proc. 35th Symp. Theory of Computing, pp.\u00a0143\u2013148 (2003)"},{"key":"9459_CR17","first-page":"430","volume-title":"SOCG \u201906: Proc. 22nd Symp. Comput. Geom.","author":"M. Kutz","year":"2006","unstructured":"Kutz, M.: Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time. In: SOCG \u201906: Proc. 22nd Symp. Comput. Geom., pp.\u00a0430\u2013438 (2006)"},{"key":"9459_CR18","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36, 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"key":"9459_CR19","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Rose, D., Tarjan, R.E.: Generalized nested dissection. SIAM J. Numer. Anal. 16, 346\u2013358 (1979)","journal-title":"SIAM J. Numer. Anal."},{"key":"9459_CR20","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0022-0000(86)90030-9","volume":"32","author":"G.L. Miller","year":"1986","unstructured":"Miller, G.L.: Finding small simple cycle separators for 2-connected planar graphs. J. Comput. Syst. Sci. 32, 265\u2013279 (1986)","journal-title":"J. Comput. Syst. Sci."},{"key":"9459_CR21","doi-asserted-by":"crossref","first-page":"978","DOI":"10.1137\/S0097539799361671","volume":"30","author":"G. Narasimhan","year":"2000","unstructured":"Narasimhan, G., Smid, M.: Approximating the stretch factor of Euclidean graphs. SIAM J. Comput. 30, 978\u2013989 (2000)","journal-title":"SIAM J. Comput."},{"key":"9459_CR22","series-title":"Lecture Notes in Computer Science","volume-title":"The Design of Dynamic Data Structures","author":"M.H. Overmars","year":"1983","unstructured":"Overmars, M.H.: The Design of Dynamic Data Structures. Lecture Notes in Computer Science, vol.\u00a0156. Springer, Berlin (1983)"},{"key":"9459_CR23","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1016\/j.dam.2008.08.002","volume":"157","author":"S. Tazari","year":"2009","unstructured":"Tazari, S., M\u00fcller-Hannemann, M.: Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation. Discrete Appl. Math. 157, 673\u2013684 (2009)","journal-title":"Discrete Appl. Math."},{"issue":"6","key":"9459_CR24","doi-asserted-by":"crossref","first-page":"993","DOI":"10.1145\/1039488.1039493","volume":"51","author":"M. Thorup","year":"2004","unstructured":"Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51(6), 993\u20131024 (2004)","journal-title":"J. ACM"},{"key":"9459_CR25","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/3-540-44676-1_3","volume-title":"ESA 2001","author":"U. Zwick","year":"2001","unstructured":"Zwick, U.: Exact and approximate distances in graphs\u2014A survey. In: ESA 2001. LNCS, vol. 2161, pp. 33\u201348. Springer, Berlin (2001)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9459-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9459-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9459-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:06Z","timestamp":1559137506000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9459-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10,15]]},"references-count":25,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["9459"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9459-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10,15]]}}}