{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:59Z","timestamp":1759637939947,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316316","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"138-151","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Almost optimal distance oracles for planar graphs"],"prefix":"10.1145","author":[{"given":"Panagiotis","family":"Charalampopoulos","sequence":"first","affiliation":[{"name":"King's College London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"additional","affiliation":[{"name":"University of Wroc\u0142aw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shay","family":"Mozes","sequence":"additional","affiliation":[{"name":"IDC Herzliya, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oren","family":"Weimann","sequence":"additional","affiliation":[{"name":"University of Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Srinivasa Rao Arikati Danny Z. Chen L. Paul Chew Gautam Das Michiel H. M. Smid and Christos D. Zaroliagis. 1996. Planar Spanners and Approximate Shortest Path Queries among Obstacles in the Plane. In 4th ESA. 514\u2013528.   Srinivasa Rao Arikati Danny Z. Chen L. Paul Chew Gautam Das Michiel H. M. Smid and Christos D. Zaroliagis. 1996. Planar Spanners and Approximate Shortest Path Queries among Obstacles in the Plane. In 4th ESA. 514\u2013528.","DOI":"10.1007\/3-540-61680-2_79"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116880"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Michael A. Bender and Martin Farach-Colton. 2000. The LCA Problem Revisited. In 4th LATIN. 88\u201394.   Michael A. Bender and Martin Farach-Colton. 2000. The LCA Problem Revisited. In 4th LATIN. 88\u201394.","DOI":"10.1007\/10719839_9"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2003.05.002"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.63"},{"volume-title":"28th International Colloquium, ICALP 2001, Crete, Greece, July 8-12, 2001, Proceedings. 140\u2013151","year":"2001","author":"Brodal Gerth St\u00f8lting","key":"e_1_3_2_1_6_1"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9459-0"},{"volume-title":"28th SODA. 2143\u20132152.","author":"Cabello Sergio","key":"e_1_3_2_1_8_1"},{"key":"e_1_3_2_1_9_1","unstructured":"Sergio Cabello Erin W. Chambers and Jeff Erickson. 2013.  Sergio Cabello Erin W. Chambers and Jeff Erickson. 2013."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Multiple-Source Shortest Paths in Embedded Graphs. SIAM J. Comput. 42 4 (2013) 1542\u20131571.  Multiple-Source Shortest Paths in Embedded Graphs. SIAM J. Comput. 42 4 (2013) 1542\u20131571.","DOI":"10.1137\/120864271"},{"key":"e_1_3_2_1_11_1","unstructured":"Timothy M. Chan and Dimitrios Skrepetos. 2017. Faster Approximate Diameter and Distance Oracles in Planar Graphs. In 25th ESA. 25:1\u201325:13.  Timothy M. Chan and Dimitrios Skrepetos. 2017. Faster Approximate Diameter and Distance Oracles in Planar Graphs. In 25th ESA. 25:1\u201325:13."},{"volume-title":"30th SODA. 2110\u2013 2123.","author":"Charalampopoulos Panagiotis","key":"e_1_3_2_1_12_1"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335359"},{"volume-title":"58th FOCS. 962\u2013973.","author":"Cohen-Addad Vincent","key":"e_1_3_2_1_14_1"},{"key":"e_1_3_2_1_15_1","unstructured":"Mark de Berg Otfried Cheong Marc J. van Kreveld and Mark H. Overmars. 2008.  Mark de Berg Otfried Cheong Marc J. van Kreveld and Mark H. Overmars. 2008."},{"key":"e_1_3_2_1_16_1","unstructured":"Computational geometry: algorithms and applications 3rd Edition. Springer. http:\/\/www.worldcat.org\/oclc\/227584184   Computational geometry: algorithms and applications 3rd Edition. Springer. http:\/\/www.worldcat.org\/oclc\/227584184"},{"volume-title":"17th DASFAA. 526\u2013543.","author":"Demiryurek Ugur","key":"e_1_3_2_1_17_1"},{"volume-title":"22nd WG. 151\u2013165.","author":"Djidjev Hristo","key":"e_1_3_2_1_18_1"},{"key":"e_1_3_2_1_19_1","unstructured":"David Eppstein and Michael T. Goodrich. 2008.  David Eppstein and Michael T. Goodrich. 2008."},{"volume-title":"16th ACM-GIS. 16.","author":"Studying","key":"e_1_3_2_1_20_1"},{"volume-title":"Proc. Symp. Theory of Graphs and its Applications. 29\u201336","year":"1963","author":"Erd\u0151s Paul","key":"e_1_3_2_1_21_1"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188904"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0037(200010)36:3<156::AID-NET2>3.0.CO;2-L"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.007"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"volume-title":"29th SODA. 515\u2013529.","author":"Gawrychowski Pawe\u0142","key":"e_1_3_2_1_26_1"},{"volume-title":"26th ISAAC. 625\u2013636.","author":"Gu Qian-Ping","key":"e_1_3_2_1_27_1"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1493"},{"key":"e_1_3_2_1_29_1","unstructured":"Shinichi Honiden Michael E. Houle Christian Sommer and Martin Wolff. 2010.  Shinichi Honiden Michael E. Houle Christian Sommer and Martin Wolff. 2010."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Approximate Shortest Path Queries Using Voronoi Duals. Trans. Computational Science 9 (2010) 28\u201353.  Approximate Shortest Path Queries Using Voronoi Duals. Trans. Computational Science 9 (2010) 28\u201353.","DOI":"10.1007\/978-3-642-16007-3_2"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3039873"},{"volume-title":"37th ICALP. 135\u2013146.","author":"Klein Philip N.","key":"e_1_3_2_1_32_1"},{"key":"e_1_3_2_1_33_1","unstructured":"Ken-ichi Kawarabayashi Christian Sommer and Mikkel Thorup. 2013.  Ken-ichi Kawarabayashi Christian Sommer and Mikkel Thorup. 2013."},{"volume-title":"23rd SODA. 550\u2013563.","author":"Approximate More Compact","key":"e_1_3_2_1_34_1"},{"volume-title":"12th SODA. 820\u2013827.","author":"Klein Philip N.","key":"e_1_3_2_1_35_1"},{"volume-title":"16th SODA. 146\u2013155.","author":"Klein Philip N.","key":"e_1_3_2_1_36_1"},{"key":"e_1_3_2_1_37_1","unstructured":"Philip N. Klein and Shay Mozes. {n. d.}. Optimization Algorithms for Planar Graphs. http:\/\/planarity.org. Book draft.  Philip N. Klein and Shay Mozes. {n. d.}. Optimization Algorithms for Planar Graphs. http:\/\/planarity.org. Book draft."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488672"},{"volume-title":"19th ESA. 155\u2013166.","author":"Lacki Jakub","key":"e_1_3_2_1_39_1"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90066-X"},{"key":"e_1_3_2_1_41_1","unstructured":"Gary L. Miller. 1984.  Gary L. Miller. 1984."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808703"},{"volume-title":"29th SODA. 477\u2013494.","author":"Mozes Shay","key":"e_1_3_2_1_43_1"},{"volume-title":"23rd SODA. 209\u2013222.","author":"Mozes Shay","key":"e_1_3_2_1_44_1"},{"volume-title":"18th ESA. 206\u2013217.","author":"Mozes Shay","key":"e_1_3_2_1_45_1"},{"volume-title":"12th WADS. 642\u2013653.","author":"Nussbaum Yahav","key":"e_1_3_2_1_46_1"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658810701587891"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/11084128X"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2530531"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039493"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Phoenix AZ USA","acronym":"STOC '19"},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316316","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316316","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:01Z","timestamp":1750204441000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316316"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":51,"alternative-id":["10.1145\/3313276.3316316","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316316","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}