{"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":1772372282768,"version":"3.50.1"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,12,7]],"date-time":"2018-12-07T00:00:00Z","timestamp":1544140800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004329","name":"Slovenian Research Agency","doi-asserted-by":"crossref","award":["Program P1-0297, Projects No. J1-8130 and No. J1-8155"],"award-info":[{"award-number":["Program P1-0297, Projects No. J1-8130 and No. J1-8155"]}],"id":[{"id":"10.13039\/501100004329","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":[[2019,4,30]]},"abstract":"<jats:p>\n            In this article, we show how to compute for\n            <jats:italic>n<\/jats:italic>\n            -vertex planar graphs in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>11\/6<\/jats:sup>\n            polylog(\n            <jats:italic>n<\/jats:italic>\n            )) expected time the diameter and the sum of the pairwise distances. The algorithms work for directed graphs with real weights and no negative cycles. In\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>15\/8<\/jats:sup>\n            polylog(\n            <jats:italic>n<\/jats:italic>\n            )) expected time, we can also compute the number of pairs of vertices at distances smaller than a given threshold. These are the first algorithms for these problems using time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>c<\/jats:italic>\n            <\/jats:sup>\n            ) for some constant\n            <jats:italic>c<\/jats:italic>\n            &lt; 2, even when restricted to undirected, unweighted planar graphs.\n          <\/jats:p>","DOI":"10.1145\/3218821","type":"journal-article","created":{"date-parts":[[2018,12,7]],"date-time":"2018-12-07T13:17:29Z","timestamp":1544188649000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs"],"prefix":"10.1145","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3183-4126","authenticated-orcid":false,"given":"Sergio","family":"Cabello","sequence":"first","affiliation":[{"name":"Department of Mathematics, FMF, University of Ljubljana, Slovenia and Department of Mathematics, IMFM, Slovenia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,12,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884463"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1120060.1712350"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 26th Canadian Conference on Computational Geometry (CCCG\u201914)","author":"Bohler Cecilia","year":"2014"},{"key":"e_1_2_1_4_1","volume-title":"Graph Theory. Graduate texts in mathematics","author":"Bondy J. A."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9459-0"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039825"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/120864271"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.02.001"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/090766863"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.93"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1882123.1882135"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1370949"},{"key":"e_1_2_1_13_1","volume-title":"3rd electronic ed. Graduate texts in mathematics","author":"Diestel Reinhard"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903)","author":"Eppstein David","year":"2003"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.007"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2399256.2399297"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102788"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175303"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175304"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1387061.1387065"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1076"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC\u201916)","volume":"63","author":"Husfeldt Thore","year":"2017"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301366"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP\u201911)","volume":"6755","author":"Klein Philip N.","year":"2011"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905)","author":"Klein P. N.","year":"2005"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488672"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721846"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009223"},{"key":"e_1_2_1_30_1","series-title":"Lecture Notes in Computer Science","volume-title":"Concrete and Abstract Voronoi Diagrams","author":"Klein Rolf"},{"key":"e_1_2_1_31_1","volume-title":"Encyclopedia of Algorithms, Ming-Yang Kao (Ed.)","author":"Klein Rolf"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.03.002"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(93)90033-3"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0716027"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_72"},{"key":"e_1_2_1_36_1","volume-title":"Faster shortest paths in dense distance graphs, with applications. CoRR abs\/1404.0977","author":"Mozes Shay","year":"2014"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095135"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 18th Annual European Symposium on Algorithms (ESA\u201910)","volume":"6347","author":"Mozes Shay","year":"2010"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993679"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167284"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/100811416"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488673"},{"key":"e_1_2_1_43_1","volume-title":"Combinatorial Optimization\u2014Polyhedra and Efficiency","author":"Schrijver A."},{"key":"e_1_2_1_44_1","volume-title":"Handbook of Discrete and Computational Geometry","author":"Snoeyink Jack","edition":"2"},{"key":"e_1_2_1_45_1","volume-title":"Handbook of Discrete and Computational Geometry","author":"Tamassia Roberto","edition":"2"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039493"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764910"},{"key":"e_1_2_1_49_1","unstructured":"Christian Wulff-Nilsen. 2010. Wiener Index Diameter and Stretch Factor of a Weighted Planar Graph in Subquadratic Time. Retrieved from http:\/\/www.diku.dk\/forskning\/phd-studiet\/phd\/ThesisChristian.pdf.  Christian Wulff-Nilsen. 2010. Wiener Index Diameter and Stretch Factor of a Weighted Planar Graph in Subquadratic Time. Retrieved from http:\/\/www.diku.dk\/forskning\/phd-studiet\/phd\/ThesisChristian.pdf."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3218821","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3218821","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:05Z","timestamp":1750212425000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3218821"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,7]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4,30]]}},"alternative-id":["10.1145\/3218821"],"URL":"https:\/\/doi.org\/10.1145\/3218821","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12,7]]},"assertion":[{"value":"2017-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}