{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:19:49Z","timestamp":1759637989844,"version":"3.40.3"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030835071"},{"type":"electronic","value":"9783030835088"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-83508-8_31","type":"book-chapter","created":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T13:05:06Z","timestamp":1627650306000},"page":"428-441","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Better Distance Labeling for Unweighted Planar Graphs"],"prefix":"10.1007","author":[{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Przemys\u0142aw","family":"Uzna\u0144ski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,31]]},"reference":[{"key":"31_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":"31_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":"31_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":"31_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":"31_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":"31_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":"31_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":"31_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":"31_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":"31_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":"31_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":"31_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":"31_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":"31_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"},{"key":"31_CR15","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":"31_CR16","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":"31_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1007\/978-3-662-53426-7_17","volume-title":"Distributed Computing","author":"P Gawrychowski","year":"2016","unstructured":"Gawrychowski, P., Kosowski, A., Uzna\u0144ski, P.: Sublinear-space distance labeling using hubs. In: Gavoille, C., Ilcinkas, D. (eds.) DISC 2016. LNCS, vol. 9888, pp. 230\u2013242. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53426-7_17"},{"key":"31_CR18","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":"31_CR19","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BFb0067362","volume-title":"Graph Theory and Applications","author":"RL Graham","year":"1972","unstructured":"Graham, R.L., Pollak, H.O.: On embedding graphs in squashed cubes. In: Alavi, Y., Lick, D.R., White, A.T. (eds.) Graph Theory and Applications. LNM, vol. 303, pp. 99\u2013110. Springer, Heidelberg (1972). https:\/\/doi.org\/10.1007\/BFb0067362"},{"key":"31_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-642-10631-6_32","volume-title":"Algorithms and Computation","author":"T-H Hsu","year":"2009","unstructured":"Hsu, T.-H., Lu, H.-I.: An optimal labeling for node connectivity. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 303\u2013310. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-10631-6_32"},{"key":"31_CR21","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":"31_CR22","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. Discret. Math. 5(4), 596\u2013603 (1992)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"31_CR23","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":"31_CR24","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":"31_CR25","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":"31_CR26","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":"31_CR27","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":"31_CR28","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":"31_CR29","doi-asserted-by":"crossref","unstructured":"Moon, J.W.: On Minimal $$n$$-Universal Graphs. vol. 7, pp. 32\u201333. Cambridge University Press, Cambridge (1965)","DOI":"10.1017\/S2040618500035139"},{"issue":"3","key":"31_CR30","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. Theor. Comput. Sci. 340(3), 577\u2013593 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"31_CR31","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":"31_CR32","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":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-83508-8_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,18]],"date-time":"2022-02-18T11:28:09Z","timestamp":1645183689000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-83508-8_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030835071","9783030835088"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-83508-8_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"31 July 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Workshop on Algorithms and Data Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 August 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 August 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/projects.cs.dal.ca\/wads2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"123","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"47","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"38% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"13","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}