{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T13:38:02Z","timestamp":1772372282579,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2019,4,11]],"date-time":"2019-04-11T00:00:00Z","timestamp":1554940800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,4,11]],"date-time":"2019-04-11T00:00:00Z","timestamp":1554940800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1814026"],"award-info":[{"award-number":["CCF-1814026"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,8]]},"DOI":"10.1007\/s00453-019-00570-z","type":"journal-article","created":{"date-parts":[[2019,4,11]],"date-time":"2019-04-11T07:24:13Z","timestamp":1554967453000},"page":"3075-3098","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Faster Approximate Diameter and Distance Oracles in Planar Graphs"],"prefix":"10.1007","volume":"81","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8093-0675","authenticated-orcid":false,"given":"Timothy M.","family":"Chan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dimitrios","family":"Skrepetos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,4,11]]},"reference":[{"issue":"2","key":"570_CR1","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1145\/1103963.1103966","volume":"1","author":"S Alstrup","year":"2005","unstructured":"Alstrup, S., Holm, J., de Lichtenberg, K., Thorup, M.: Maintaining information in fully dynamic trees with top trees. ACM Trans. Algorithms 1(2), 243\u2013264 (2005)","journal-title":"ACM Trans. Algorithms"},{"key":"570_CR2","doi-asserted-by":"crossref","unstructured":"Berman, P., Kasiviswanathan, S.P.: Faster approximation of distances in graphs. In: Proceedings of the 10th International Symposium on Algorithms and Data Structures (WADS), pp. 541\u2013552 (2007)","DOI":"10.1007\/978-3-540-73951-7_47"},{"key":"570_CR3","doi-asserted-by":"crossref","unstructured":"Busch, C., LaFortune, R., Tirthapura, S.: Improved sparse covers for graphs excluding a fixed minor. In: Proceedings of the 26th ACM Symposium on Principles of Distributed Computing (PODC), pp. 61\u201370 (2007)","DOI":"10.1145\/1281100.1281112"},{"key":"570_CR4","doi-asserted-by":"crossref","unstructured":"Cabello, S.: Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. In: Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2143\u20132152 (2017)","DOI":"10.1137\/1.9781611974782.139"},{"key":"570_CR5","unstructured":"Cabello, S.: Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. CoRR, (2017) \n                    arXiv:1702.07815"},{"key":"570_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2344422.2344424","volume":"8","author":"TM Chan","year":"2012","unstructured":"Chan, T.M.: All-pairs shortest paths for unweighted undirected graphs in $$o(mn)$$ time. ACM Trans. Algorithms 8, 1\u201317 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"570_CR7","unstructured":"Chan, T.M., Skrepetos, D.: Faster approximate diameter and distance oracles in planar graphs. In: Proceeding of the 25th European Symposium on Algorithms (ESA), pp. 25:1\u201325:13 (2017)"},{"issue":"5","key":"570_CR8","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"KL Clarkson","year":"1989","unstructured":"Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry, II. Discrete Comput Geom 4(5), 387\u2013421 (1989)","journal-title":"Discrete Comput Geom"},{"issue":"1","key":"570_CR9","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF02122694","volume":"10","author":"H De Fraysseix","year":"1990","unstructured":"De Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41\u201351 (1990)","journal-title":"Combinatorica"},{"issue":"1","key":"570_CR10","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0022-0000(89)90034-2","volume":"38","author":"JR Driscoll","year":"1989","unstructured":"Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. J. Comput. Syst. Sci. 38(1), 86\u2013124 (1989)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"570_CR11","doi-asserted-by":"publisher","first-page":"283","DOI":"10.7155\/jgaa.00014","volume":"3","author":"D Eppstein","year":"1999","unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl. 3(3), 283\u2013309 (1999)","journal-title":"J. Graph Algorithms Appl."},{"key":"570_CR12","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."},{"issue":"3","key":"570_CR13","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"ML Fredman","year":"1993","unstructured":"Fredman, M.L., Willard, D.E.: Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47(3), 424\u2013436 (1993)","journal-title":"J. Comput. Syst. Sci."},{"key":"570_CR14","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P., Kaplan, H., Mozes, S., Sharir, M., Weimann, O.: Voronoi diagrams on planar graphs, and computing the diameter in deterministic $${\\widetilde{O}}\\left(n^{5\/3}\\right)$$ time. In: Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 495\u2013514 (2018)","DOI":"10.1137\/1.9781611975031.33"},{"key":"570_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 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 515\u2013529 (2018)","DOI":"10.1137\/1.9781611975031.34"},{"key":"570_CR16","doi-asserted-by":"crossref","unstructured":"Gu, Q.-P., Xu, G.: Constant query time $$(1+\\varepsilon )$$-approximate distance oracle for planar graphs. In: Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC), pp. 625\u2013636 (2015). Theoretical Computer Science (to appear)","DOI":"10.1007\/978-3-662-48971-0_53"},{"issue":"1","key":"570_CR17","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"MR Henzinger","year":"1997","unstructured":"Henzinger, M.R., Philip, K., Satish, R., Subramanian, S.: Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 55(1), 3\u201323 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"570_CR18","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Klein, P.N., Sommer, C.: Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs. In: Proceedings of the 38th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 135\u2013146 (2011)","DOI":"10.1007\/978-3-642-22006-7_12"},{"key":"570_CR19","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Sommer, C., Thorup, M.: More compact oracles for approximate distances in undirected planar graphs. In: Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 550\u2013563 (2013)","DOI":"10.1137\/1.9781611973105.40"},{"key":"570_CR20","unstructured":"Klein, P.N.: Preprocessing an undirected planar network to enable fast approximate distance queries. In: Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 820\u2013827 (2002)"},{"key":"570_CR21","unstructured":"Klein, P.N.: Multiple-source shortest paths in planar graphs. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 146\u2013155 (2005)"},{"key":"570_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-52055-4","volume-title":"Concrete and Abstract Voronoi Diagrams, Volume 400 of Lecture Notes in Computer Science","author":"R Klein","year":"1989","unstructured":"Klein, R.: Concrete and Abstract Voronoi Diagrams, Volume 400 of Lecture Notes in Computer Science. Springer, New York (1989)"},{"issue":"3","key":"570_CR23","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0925-7721(93)90033-3","volume":"3","author":"R Klein","year":"1993","unstructured":"Klein, R., Mehlhorn, K., Meiser, S.: Randomized incremental construction of abstract Voronoi diagrams. Comput. Geom. 3(3), 157\u2013184 (1993)","journal-title":"Comput. Geom."},{"issue":"2","key":"570_CR24","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"RJ Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"key":"570_CR25","volume-title":"Computational Geometry: An Introduction Through Randomized Algorithms","author":"K Mulmuley","year":"1994","unstructured":"Mulmuley, K.: Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Upper Saddle River (1994)"},{"key":"570_CR26","unstructured":"Schnyder, W: Embedding planar graphs on the grid. In: Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 138\u2013148 (1990)"},{"issue":"3","key":"570_CR27","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"570_CR28","doi-asserted-by":"publisher","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"},{"issue":"1","key":"570_CR29","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1145\/2764910","volume":"12","author":"O Weimann","year":"2016","unstructured":"Weimann, O., Yuster, R.: Approximating the diameter of planar graphs in near linear time. ACM Trans. Algorithms 12(1), 12 (2016)","journal-title":"ACM Trans. Algorithms"},{"key":"570_CR30","unstructured":"Wulff-Nilsen, C.: Algorithms for planar graphs and graphs in metric spaces. Ph.D. thesis, University of Copenhagen (2010)"},{"key":"570_CR31","doi-asserted-by":"crossref","unstructured":"Wulff-Nilsen, C.: Approximate distance oracles for planar graphs with improved query time-space tradeoff. In: Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 351\u2013362 (2016)","DOI":"10.1137\/1.9781611974331.ch26"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00570-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00570-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00570-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:34:56Z","timestamp":1589697296000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00570-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,11]]},"references-count":31,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2019,8]]}},"alternative-id":["570"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00570-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,11]]},"assertion":[{"value":"22 May 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 April 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 April 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}