{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T21:47:38Z","timestamp":1780436858580,"version":"3.54.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T00:00:00Z","timestamp":1648598400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["794\/13, 592\/17, and 810\/21"],"award-info":[{"award-number":["794\/13, 592\/17, and 810\/21"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,4,30]]},"abstract":"<jats:p>\n            We consider exact distance oracles for directed weighted planar graphs in the presence of failing vertices. Given a source vertex\n            <jats:italic>u<\/jats:italic>\n            , a target vertex\n            <jats:italic>v<\/jats:italic>\n            and a set\n            <jats:italic>X<\/jats:italic>\n            of\n            <jats:italic>k<\/jats:italic>\n            failed vertices, such an oracle returns the length of a shortest\n            <jats:italic>u<\/jats:italic>\n            -to-\n            <jats:italic>v<\/jats:italic>\n            path that avoids all vertices in\n            <jats:italic>X<\/jats:italic>\n            . We propose oracles that can handle any number\n            <jats:italic>k<\/jats:italic>\n            of failures. We show several tradeoffs between space, query time, and preprocessing time. In particular, for a directed weighted planar graph with\n            <jats:italic>n<\/jats:italic>\n            vertices and any constant\n            <jats:italic>k<\/jats:italic>\n            , we show an \u00d5(\n            <jats:italic>n<\/jats:italic>\n            )-size, \u00d5(\u221a\n            <jats:italic>n<\/jats:italic>\n            )-query-time oracle.\n            <jats:xref ref-type=\"fn\">\n              <jats:sup>1<\/jats:sup>\n            <\/jats:xref>\n            We then present a space vs. query time tradeoff: for any\n            <jats:italic>q<\/jats:italic>\n            \u03b5 [ 1,\u221a\n            <jats:italic>n<\/jats:italic>\n            ], we propose an oracle of size\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>k+1+o(1)<\/jats:sup>\n            \/\n            <jats:italic>\n              q\n              <jats:sup>2k<\/jats:sup>\n            <\/jats:italic>\n            that answers queries in \u00d5(\n            <jats:italic>q<\/jats:italic>\n            ) time. For single vertex failures (\n            <jats:italic>k<\/jats:italic>\n            = 1), our\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2+o(1)<\/jats:sup>\n            \/\n            <jats:italic>q<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            -size, \u00d5(\n            <jats:italic>q<\/jats:italic>\n            )-query-time oracle improves over the previously best known tradeoff of Baswana et\u00a0al.\u00a0SODA 2012 by polynomial factors for\n            <jats:italic>q<\/jats:italic>\n            \u2265\n            <jats:italic>\n              n\n              <jats:sup>t<\/jats:sup>\n            <\/jats:italic>\n            , for any\n            <jats:italic>t<\/jats:italic>\n            \u2208 (0,1\/2]. For multiple failures, no planarity exploiting results were previously known.\n          <\/jats:p>","DOI":"10.1145\/3511541","type":"journal-article","created":{"date-parts":[[2022,2,8]],"date-time":"2022-02-08T22:18:47Z","timestamp":1644358727000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Exact Distance Oracles for Planar Graphs with Failing Vertices"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6024-1557","authenticated-orcid":false,"given":"Panagiotis","family":"Charalampopoulos","sequence":"first","affiliation":[{"name":"Reichman University, Herzliya, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9262-1821","authenticated-orcid":false,"given":"Shay","family":"Mozes","sequence":"additional","affiliation":[{"name":"Reichman University, Herzliya, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4646-8373","authenticated-orcid":false,"given":"Benjamin","family":"Tebeka","sequence":"additional","affiliation":[{"name":"Reichman University, Herzliya, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,3,30]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.58"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214084"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61680-2_79"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-79527-6_18"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.20"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536431"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2684068"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9459-0"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/120864271"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316316"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2020.31"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.127"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335359"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.93"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705429847"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-62559-3_14"},{"key":"e_1_3_2_18_2","first-page":"506","volume-title":"20th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009","author":"Duan Ran","year":"2009","unstructured":"Ran Duan and Seth Pettie. 2009. Dual-failure distance and connectivity oracles. In 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009. 506\u2013515. http:\/\/dl.acm.org\/citation.cfm?id=1496770.1496826."},{"key":"e_1_3_2_19_2","article-title":"Maintaining exact distances under multiple edge failures","volume":"2111","author":"Duan Ran","year":"2021","unstructured":"Ran Duan and Hanlin Ren. 2021. Maintaining exact distances under multiple edge failures. CoRR abs\/2111.03360 (2021). arXiv:2111.03360https:\/\/arxiv.org\/abs\/2111.03360.","journal-title":"CoRR"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1824777.1824784"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795290477"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188904"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.007"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ISAAC.2021.25"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1193402"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.61"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.34"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959899"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993679"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3039873"},{"key":"e_1_3_2_32_2","volume-title":"2nd Symposium on Networked Systems Design and Implementation (NSDI 2005)","author":"Kim Young-Jin","year":"2005","unstructured":"Young-Jin Kim, Ramesh Govindan, Brad Karp, and Scott Shenker. 2005. Geographic routing made practical. In 2nd Symposium on Networked Systems Design and Implementation (NSDI 2005). USENIX. http:\/\/www.usenix.org\/events\/nsdi05\/tech\/kim.html."},{"key":"e_1_3_2_33_2","first-page":"146","volume-title":"16th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005","author":"Klein Philip N.","year":"2005","unstructured":"Philip N. Klein. 2005. Multiple-source shortest paths in planar graphs. In 16th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005. 146\u2013155. http:\/\/dl.acm.org\/citation.cfm?id=1070432.1070454."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488672"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721846"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.149"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808703"},{"key":"e_1_3_2_38_2","volume-title":"M\u00e9moire sur la th\u00e9orie des d\u00e9blais et des remblais","author":"Monge Gaspard","year":"1781","unstructured":"Gaspard Monge. 1781. M\u00e9moire sur la th\u00e9orie des d\u00e9blais et des remblais. De l\u2019Imprimerie Royale."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.19"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15781-3_18"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301287"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00034"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2438645.2438646"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.62"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3511541","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3511541","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:51:04Z","timestamp":1750182664000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3511541"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,30]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4,30]]}},"alternative-id":["10.1145\/3511541"],"URL":"https:\/\/doi.org\/10.1145\/3511541","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,30]]},"assertion":[{"value":"2020-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}