{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T19:58:06Z","timestamp":1791316686187,"version":"4.3.1"},"reference-count":54,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-16-CE40-0023"],"award-info":[{"award-number":["ANR-16-CE40-0023"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-17-CE40-0015"],"award-info":[{"award-number":["ANR-17-CE40-0015"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["677651"],"award-info":[{"award-number":["677651"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:p>An adjacency labeling scheme for a given class of graphs is an algorithm that, for every graph $G$ from the class, assigns bit strings (labels) to vertices of $G$ so that for any two vertices $u,v$, whether $u$ and $v$ are adjacent can be determined by a fixed procedure that examines only their labels. It is known that planar graphs with $n$ vertices admit a labeling scheme with labels of bit length $(2+o(1))\\log{n}$. In this work we improve this bound by designing a labeling scheme with labels of bit length $(\\frac{4}{3}+o(1))\\log{n}$. All the labels of the input graph can be computed in polynomial time, while adjacency can be decided from the labels in constant time. In graph-theoretical terms, this implies an explicit construction of a graph on $n^{4\/3+o(1)}$ vertices that contains all planar graphs on $n$ vertices as induced subgraphs, improving the previous best upper bound of $n^{2+o(1)}$. Our labeling scheme can be generalized to larger classes of topologically constrained graphs, for instance, to graphs embeddable in any fixed surface or to $k$-planar graphs for any fixed $k$, at the cost of larger second-order terms.<\/jats:p>","DOI":"10.1137\/20m1330464","type":"journal-article","created":{"date-parts":[[2022,8,31]],"date-time":"2022-08-31T10:05:22Z","timestamp":1661940322000},"page":"2082-2099","source":"Crossref","is-referenced-by-count":10,"title":["Shorter Labeling Schemes for Planar Graphs"],"prefix":"10.1137","volume":"36","author":[{"given":"Marthe","family":"Bonamy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cyril","family":"Gavoille","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2022,8,31]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1145\/2818694"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2019.10.030"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00710-w"},{"key":"atypb4","first-page":"375","volume-title":"ICALP 2014","author":"Adjiashvili D.","year":"2014"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(87)90055-7"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-017-0396-9"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1145\/3088513"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch25"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1155-5"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.72"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/16M1105967"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2002.1181882"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73486-8"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.27"},{"key":"atypb16","first-page":"143","volume-title":"SIROCCO 2006","author":"Bonichon N.","year":"2006"},{"key":"atypb17","volume-title":"An Optimal Algorithm for Product Structure in Planar Graphs, preprint, arXiv:2202.08870v1 [cs.DS]","author":"Bose P.","year":"2022"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-009-0860-x"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s004930200017"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9196-9"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190140408"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001139"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/3477542"},{"key":"atypb24","volume-title":"Adv. Combin., (2020","author":"Dujmovi\u0107 V.","year":"1908"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1145\/3385731"},{"key":"atypb26","volume-title":"Graph Product Structure for Non-Minor-Closed Classes, preprint, arXiv:1907.05168 [math.CO]","author":"Dujmovi\u0107 V.","year":"2020"},{"key":"atypb27","volume-title":"Notes on Graph Product Structure Theory, preprint, arXiv:2001.08860 [math.CO]","author":"Dvo\u0159\u00e1k Z.","year":"2020"},{"key":"atypb28","volume-title":"Sparse Universal Graphs for Planarity, preprint, arXiv:2010.05779v1 [math.CO]","author":"Esperet L.","year":"2021"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.04.020"},{"key":"atypb30","first-page":"757","volume-title":"ICALP 2001","author":"Fraigniaud P.","year":"2076"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1145\/2794076"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087804"},{"key":"atypb33","first-page":"582","volume-title":"ESA 2007","author":"Gavoille C.","year":"2007"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1137\/050635006"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-002-0073-5"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977066.3"},{"key":"atypb37","first-page":"230","volume-title":"DISC 2016","author":"Gawrychowski P.","year":"2016"},{"key":"atypb38","volume-title":"A Note on Distance Labeling in Planar Graphs, preprint, arXiv:1611.06529v1 [cs.DS]","author":"Gawrychowski P.","year":"2016"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.12"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62244"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703433912"},{"key":"atypb42","first-page":"141","volume":"88","author":"Koebe P.","year":"1936","journal-title":"Berichte Ber. Verhand. S\u00e4chsische Akad. Wiss. Leipzig Math. Phys."},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00793-5"},{"key":"atypb44","first-page":"579","volume-title":"MFCS 2000","author":"Peleg D.","year":"1893"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.03.015"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90053-1"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767409"},{"key":"atypb49","unstructured":"N. Rotbart,\n                      New Ideas on Labeling Schemes\n                      , Ph.D. thesis, University of Copenhagen, 2016,http:\/\/www.academia.edu\/33855491\/New_Ideas_on_Labeling_Schemes."},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1007\/BF00353652"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1090\/fim\/019"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90061-4"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378581"},{"key":"atypb54","volume-title":"An Improved Planar Graph Product Structure Theorem, preprint, arXiv:2108.00198v1 [math.CO]","author":"Ueckerdt T.","year":"2021"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1330464","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:38:33Z","timestamp":1787319513000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1330464"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,31]]},"references-count":54,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["10.1137\/20M1330464"],"URL":"https:\/\/doi.org\/10.1137\/20m1330464","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,31]]}}}