{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:45:52Z","timestamp":1781077552747,"version":"3.54.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T00:00:00Z","timestamp":1684108800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T00:00:00Z","timestamp":1684108800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A distance labeling scheme is an assignment of labels, that is, binary strings, to all nodes of a graph, so that the distance between any two nodes can be computed from their labels without any additional information about the graph. The goal is to minimize the maximum length of a label as a function of the number of nodes. A major open problem in this area is to determine the complexity of distance labeling in unweighted planar (undirected) graphs. It is known that, in such a graph on <jats:italic>n<\/jats:italic> nodes, some labels must consist of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varOmega (n^{1\/3})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03a9<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>\/<\/mml:mo>\n                        <mml:mn>3<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> bits, but the best known labeling scheme constructs labels of length <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\sqrt{n}\\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msqrt>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msqrt>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> (Gavoille, Peleg, P\u00e9rennes, and Raz in J Algorithms 53:85\u2013112, 2004). For weighted planar graphs with edges of length polynomial in <jats:italic>n<\/jats:italic>, we know that labels of length <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varOmega (\\sqrt{n}\\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03a9<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msqrt>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msqrt>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> are necessary (Abboud and Dahlgaard in FOCS, 2016). Surprisingly, we do not know if distance labeling for weighted planar graphs with edges of length polynomial in <jats:italic>n<\/jats:italic> is harder than distance labeling for unweighted planar graphs. We prove that this is indeed the case by designing a distance labeling scheme for unweighted planar graphs on <jats:italic>n<\/jats:italic> nodes with labels consisting of <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\sqrt{n})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msqrt>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msqrt>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> bits with a simple and (in our opinion) elegant method. We also show how to extend this to graphs with small weight and (unweighted) graphs with bounded genus. We augment the construction for unweighted planar graphs with a mechanism (based on Voronoi diagrams) that allows us to compute the distance between two nodes in only polylogarithmic time while increasing the length to <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\sqrt{n\\log n})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msqrt>\n                      <mml:mrow>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mo>log<\/mml:mo>\n                        <mml:mi>n<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:msqrt>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The previous scheme required <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varOmega (\\sqrt{n})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03a9<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msqrt>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msqrt>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time to answer a query in this model.<\/jats:p>","DOI":"10.1007\/s00453-023-01133-z","type":"journal-article","created":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T14:53:11Z","timestamp":1684162391000},"page":"1805-1823","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Better Distance Labeling for Unweighted Planar Graphs"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6993-5440","authenticated-orcid":false,"given":"Pawe\u0142","family":"Gawrychowski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Przemys\u0142aw","family":"Uzna\u0144ski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,5,15]]},"reference":[{"key":"1133_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Dahlgaard, S.: Popular conjectures as a barrier for dynamic planar graph algorithms. In: 57th FOCS, pp. 477\u2013486 (2016)","DOI":"10.1109\/FOCS.2016.58"},{"key":"1133_CR2","doi-asserted-by":"crossref","unstructured":"Abboud, A., Gawrychowski, P., Mozes, S., Weimann, O.: Near-optimal compression for the planar graph metric. In: 29th SODA, pp. 530\u2013549 (2018)","DOI":"10.1137\/1.9781611975031.35"},{"key":"1133_CR3","doi-asserted-by":"crossref","unstructured":"Alon, N., Nenadov, R.: Optimal induced universal graphs for bounded-degree graphs. In: 28th SODA, pp. 1149\u20131157 (2017)","DOI":"10.1137\/1.9781611974782.74"},{"key":"1133_CR4","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Dahlgaard, S., Knudsen, M.B.T.: Optimal induced universal graphs and adjacency labeling for trees. In: 56th FOCS, pp. 1311\u20131326 (2015)","DOI":"10.1109\/FOCS.2015.84"},{"key":"1133_CR5","unstructured":"Alstrup, S., Dahlgaard, S., Knudsen, M.B.T., Porat, E.: Sublinear distance labeling. In: 24th ESA, pp. 5:1\u20135:15 (2016)"},{"key":"1133_CR6","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Gavoille, C., Halvorsen, E.B., Petersen, H.: Simpler, faster and shorter labels for distances in graphs. In: 27th SODA, pp. 338\u2013350 (2016)","DOI":"10.1137\/1.9781611974331.ch25"},{"key":"1133_CR7","unstructured":"Alstrup, S., G\u00f8rtz, I.L., Halvorsen, E.B., Porat, E.: Distance labeling schemes for trees. In: 43rd ICALP, pp. 132:1\u2013132:16 (2016)"},{"key":"1133_CR8","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Kaplan, H., Thorup, M., Zwick, U.: Adjacency labeling schemes and induced-universal graphs. In: 47th STOC, pp. 625\u2013634 (2015)","DOI":"10.1145\/2746539.2746545"},{"key":"1133_CR9","doi-asserted-by":"crossref","unstructured":"Bonamy, M., Gavoille, C., Pilipczuk, M.: Shorter labeling schemes for planar graphs. In: 30th SODA, pp. 446\u2013462 (2020)","DOI":"10.1137\/1.9781611975994.27"},{"key":"1133_CR10","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/j.endm.2007.01.022","volume":"28","author":"N Bonichon","year":"2007","unstructured":"Bonichon, N., Gavoille, C., Labourel, A.: Short labels by traversal and jumping. Electron. Notes Discret. Math. 28, 153\u2013160 (2007)","journal-title":"Electron. Notes Discret. Math."},{"issue":"2","key":"1133_CR11","doi-asserted-by":"publisher","first-page":"21:1","DOI":"10.1145\/3218821","volume":"15","author":"S Cabello","year":"2019","unstructured":"Cabello, S.: Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. ACM Trans. Algorithms 15(2), 21:1-21:38 (2019)","journal-title":"ACM Trans. Algorithms"},{"key":"1133_CR12","doi-asserted-by":"crossref","unstructured":"Charalampopoulos, P., Gawrychowski, P., Mozes, S., Weimann, O.: Almost optimal distance oracles for planar graphs. In: 51st STOC, pp. 138\u2013151. ACM (2019)","DOI":"10.1145\/3313276.3316316"},{"key":"1133_CR13","doi-asserted-by":"crossref","unstructured":"Dujmovic, V., Esperet, L., Gavoille, C., Joret, G., Micek, P., Morin, P.: Adjacency labelling for planar graphs (and beyond). In: 61st FOCS, pp. 577\u2013588. IEEE (2020)","DOI":"10.1109\/FOCS46700.2020.00060"},{"issue":"2","key":"1133_CR14","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1109\/TIT.1975.1055349","volume":"21","author":"P Elias","year":"1975","unstructured":"Elias, P.: Universal codeword sets and representations of the integers. IEEE Trans. Inf. Theory 21(2), 194\u2013203 (1975)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"1133_CR15","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s00454-003-2948-z","volume":"31","author":"J Erickson","year":"2004","unstructured":"Erickson, J., Har-Peled, S.: Optimally cutting a surface into a disk. Discret. Comput. Geom. 31(1), 37\u201359 (2004)","journal-title":"Discret. Comput. Geom."},{"key":"1133_CR16","doi-asserted-by":"crossref","unstructured":"Freedman, O., Gawrychowski, P., Nicholson, P.K., Weimann, O.: Optimal distance labeling schemes for trees. In: 36th PODC, pp. 185\u2013194 (2017)","DOI":"10.1145\/3087801.3087804"},{"issue":"1","key":"1133_CR17","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.jalgor.2004.05.002","volume":"53","author":"C Gavoille","year":"2004","unstructured":"Gavoille, C., Peleg, D., P\u00e9rennes, S., Raz, R.: Distance labeling in graphs. J. Algorithms 53(1), 85\u2013112 (2004)","journal-title":"J. Algorithms"},{"key":"1133_CR18","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P., Kosowski, A., Uzna\u0144ski, P.: Sublinear-space distance labeling using hubs. In: 30th DISC, pp. 230\u2013242 (2016)","DOI":"10.1007\/978-3-662-53426-7_17"},{"key":"1133_CR19","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P., Mozes, S., Weimann, O., Wulff-Nilsen, C.: Better tradeoffs for exact distance oracles in planar graphs. In: 29th SODA, pp. 515\u2013529. SIAM (2018)","DOI":"10.1137\/1.9781611975031.34"},{"key":"1133_CR20","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P., Uznanski, P.: Better distance labeling for unweighted planar graphs. In: 17th WADS, pp. 428\u2013441. Springer (2021)","DOI":"10.1007\/978-3-030-83508-8_31"},{"key":"1133_CR21","doi-asserted-by":"crossref","unstructured":"Graham, R., Pollak, H.: On embedding graphs in squashed cubes. In: Graph Theory and Applications. Lecture Notes in Mathematics, vol. 303, pp. 99\u2013110. Springer, Berlin Heidelberg (1972)","DOI":"10.1007\/BFb0067362"},{"key":"1133_CR22","doi-asserted-by":"crossref","unstructured":"Hsu, T., Lu, H.: An optimal labeling for node connectivity. In: 20th ISAAC, pp. 303\u2013310 (2009)","DOI":"10.1007\/978-3-642-10631-6_32"},{"issue":"2","key":"1133_CR23","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1137\/0401020","volume":"1","author":"JP Hutchinson","year":"1988","unstructured":"Hutchinson, J.P.: On short noncontractible cycles in embedded graphs. SIAM J. Discret. Math. 1(2), 185\u2013192 (1988)","journal-title":"SIAM J. Discret. Math."},{"key":"1133_CR24","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: 30th FOCS, pp. 549\u2013554. IEEE Computer Society (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"issue":"4","key":"1133_CR25","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1137\/0405049","volume":"5","author":"S Kannan","year":"1992","unstructured":"Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. SIAM J. Discrete Math. 5(4), 596\u2013603 (1992)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"1133_CR26","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1137\/S0097539703433912","volume":"34","author":"M Katz","year":"2004","unstructured":"Katz, M., Katz, N.A., Korman, A., Peleg, D.: Labeling schemes for flow and connectivity. SIAM J. Comput. 34(1), 23\u201340 (2004)","journal-title":"SIAM J. Comput."},{"key":"1133_CR27","doi-asserted-by":"crossref","unstructured":"Klein, P.N., Mozes, S., Sommer, C.: Structured recursive separator decompositions for planar graphs in linear time. In: 45th STOC, pp. 505\u2013514. ACM (2013)","DOI":"10.1145\/2488608.2488672"},{"issue":"2","key":"1133_CR28","doi-asserted-by":"publisher","first-page":"39:1","DOI":"10.1145\/1721837.1721855","volume":"6","author":"A Korman","year":"2010","unstructured":"Korman, A.: Labeling schemes for vertex connectivity. ACM Trans. Algorithms 6(2), 39:1-39:10 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"1133_CR29","doi-asserted-by":"crossref","unstructured":"Kosowski, A., Uzna\u0144ski, P., Viennot, L.: Hardness of exact distance queries in sparse graphs through hub labeling. In: 38th PODC, pp. 272\u2013279 (2019)","DOI":"10.1145\/3293611.3331625"},{"issue":"3","key":"1133_CR30","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"RJ Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1133_CR31","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0022-0000(86)90030-9","volume":"32","author":"GL Miller","year":"1986","unstructured":"Miller, G.L.: Finding small simple cycle separators for 2-connected planar graphs. J. Comput. Syst. Sci. 32(3), 265\u2013279 (1986)","journal-title":"J. Comput. Syst. Sci."},{"key":"1133_CR32","first-page":"32","volume-title":"On minimal $$n$$-universal graphs","author":"JW Moon","year":"1965","unstructured":"Moon, J.W.: On minimal $$n$$-universal graphs, pp. 32\u201333. Cambridge University Press (1965)"},{"issue":"3","key":"1133_CR33","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1016\/j.tcs.2005.03.015","volume":"340","author":"D Peleg","year":"2005","unstructured":"Peleg, D.: Informative labeling schemes for graphs. Theory Comput. Sci. 340(3), 577\u2013593 (2005)","journal-title":"Theory Comput. Sci."},{"key":"1133_CR34","unstructured":"Petersen, C., Rotbart, N., Simonsen, J.G., Wulff-Nilsen, C.: Near-optimal adjacency labeling scheme for power-law graphs. In: 43rd ICALP, pp. 133:1\u2013133:15 (2016)"},{"issue":"14","key":"1133_CR35","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1016\/j.ipl.2011.04.006","volume":"111","author":"O Weimann","year":"2011","unstructured":"Weimann, O., Peleg, D.: A note on exact distance labeling. Inf. Process. Lett. 111(14), 671\u2013673 (2011)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01133-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01133-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01133-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,27]],"date-time":"2023-05-27T03:35:02Z","timestamp":1685158502000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01133-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,15]]},"references-count":35,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["1133"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01133-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,15]]},"assertion":[{"value":"28 January 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 January 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 May 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}