{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T12:16:32Z","timestamp":1768738592173,"version":"3.49.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2021,10,5]],"date-time":"2021-10-05T00:00:00Z","timestamp":1633392000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"name":"French ANR","award":["ANR-16-CE40-0009-01, ANR-18-CE40-0032, ANR-16-CE40-0023 and ANR-17-CE40-0015"],"award-info":[{"award-number":["ANR-16-CE40-0009-01, ANR-18-CE40-0032, ANR-16-CE40-0023 and ANR-17-CE40-0015"]}]},{"name":"Wallonia-Brussels Federation of Belgium"},{"name":"National Fund for Scientific Research"},{"name":"Polish National Science Center","award":["UMO-2018\/31\/G\/ST1\/03718"],"award-info":[{"award-number":["UMO-2018\/31\/G\/ST1\/03718"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>\n            We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an\n            <jats:italic>n<\/jats:italic>\n            -vertex planar graph\n            <jats:italic>G<\/jats:italic>\n            is assigned a (1 + o(1)) log\n            <jats:sub>2<\/jats:sub>\n            <jats:italic>n<\/jats:italic>\n            -bit label and the labels of two vertices\n            <jats:italic>u<\/jats:italic>\n            and\n            <jats:italic>v<\/jats:italic>\n            are sufficient to determine if\n            <jats:italic>uv<\/jats:italic>\n            is an edge of\n            <jats:italic>G<\/jats:italic>\n            . This is optimal up to the lower order term and is the first such asymptotically optimal result. An alternative, but equivalent, interpretation of this result is that, for every positive integer\n            <jats:italic>n<\/jats:italic>\n            , there exists a graph\n            <jats:italic>U<\/jats:italic>\n            <jats:sub>n<\/jats:sub>\n            with\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1+o(1)<\/jats:sup>\n            vertices such that every\n            <jats:italic>n<\/jats:italic>\n            -vertex planar graph is an induced subgraph of\n            <jats:italic>U<\/jats:italic>\n            <jats:sub>n<\/jats:sub>\n            . These results generalize to a number of other graph classes, including bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and\n            <jats:italic>k<\/jats:italic>\n            -planar graphs.\n          <\/jats:p>","DOI":"10.1145\/3477542","type":"journal-article","created":{"date-parts":[[2021,10,5]],"date-time":"2021-10-05T20:01:15Z","timestamp":1633464075000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["Adjacency Labelling for Planar Graphs (and Beyond)"],"prefix":"10.1145","volume":"68","author":[{"given":"Vida","family":"Dujmovi\u0107","sequence":"first","affiliation":[{"name":"University of Ottawa, Ottawa, Canada"}]},{"given":"Louis","family":"Esperet","sequence":"additional","affiliation":[{"name":"CNRS, Univ. Grenoble Alpes, Grenoble, France"}]},{"given":"Cyril","family":"Gavoille","sequence":"additional","affiliation":[{"name":"University of Bordeaux, LaBRI, Bordeaux, France"}]},{"given":"Gwena\u00ebl","family":"Joret","sequence":"additional","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles, Brussels, Belgium"}]},{"given":"Piotr","family":"Micek","sequence":"additional","affiliation":[{"name":"Jagiellonian University, Krak\u00f3w, Poland"}]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[{"name":"Carleton University, Ottawa, Canada"}]}],"member":"320","published-online":{"date-parts":[[2021,10,5]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (LIPIcs), Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl (Eds.)","volume":"80","author":"Abrahamsen Mikkel","year":"2017","unstructured":"Mikkel Abrahamsen , Stephen Alstrup , Jacob Holm , Mathias B\u00e6k Tejs Knudsen , and Morten St\u00f6ckel . 2017 . Near-optimal induced universal graphs for bounded degree graphs . In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (LIPIcs), Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl (Eds.) , Vol. 80 . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 128:1\u2013128:14. DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP. 2017.128 10.4230\/LIPIcs.ICALP.2017.128 Mikkel Abrahamsen, Stephen Alstrup, Jacob Holm, Mathias B\u00e6k Tejs Knudsen, and Morten St\u00f6ckel. 2017. Near-optimal induced universal graphs for bounded degree graphs. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (LIPIcs), Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl (Eds.), Vol. 80. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 128:1\u2013128:14. DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.128"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (Lecture Notes in Computer Science)","author":"Adjiashvili David","unstructured":"David Adjiashvili and Noy Rotbart . 2014. Labeling schemes for bounded degree graphs . In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (Lecture Notes in Computer Science) , Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias (Eds.), Vol. 8573 . Springer , 375\u2013386. DOI:DOI:https:\/\/doi.org\/10.1007\/978-3-662-43951-7_32 10.1007\/978-3-662-43951-7_32 David Adjiashvili and Noy Rotbart. 2014. Labeling schemes for bounded degree graphs. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (Lecture Notes in Computer Science), Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias (Eds.), Vol. 8573. Springer, 375\u2013386. DOI:DOI:https:\/\/doi.org\/10.1007\/978-3-662-43951-7_32"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-017-0396-9"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3088513"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 24th Annual European Symposium on Algorithms (LIPIcs), Piotr Sankowski and Christos D. Zaroliagis (Eds.)","volume":"57","author":"Alstrup Stephen","year":"2016","unstructured":"Stephen Alstrup , S\u00f8ren Dahlgaard , Mathias B\u00e6k Tejs Knudsen , and Ely Porat . 2016 . Sublinear distance labeling . In Proceedings of the 24th Annual European Symposium on Algorithms (LIPIcs), Piotr Sankowski and Christos D. Zaroliagis (Eds.) , Vol. 57 . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 5:1\u20135:15. DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ESA. 2016.5 10.4230\/LIPIcs.ESA.2016.5 Stephen Alstrup, S\u00f8ren Dahlgaard, Mathias B\u00e6k Tejs Knudsen, and Ely Porat. 2016. Sublinear distance labeling. In Proceedings of the 24th Annual European Symposium on Algorithms (LIPIcs), Piotr Sankowski and Christos D. Zaroliagis (Eds.), Vol. 57. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 5:1\u20135:15. DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2016.5"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884460"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (LIPIcs), Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi (Eds.)","volume":"55","author":"Alstrup Stephen","year":"2016","unstructured":"Stephen Alstrup , Inge Li G\u00f8rtz , Esben Bistrup Halvorsen , and Ely Porat . 2016 . Distance labeling schemes for trees . In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (LIPIcs), Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi (Eds.) , Vol. 55 . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 132:1\u2013132:16. DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP. 2016.132 10.4230\/LIPIcs.ICALP.2016.132 Stephen Alstrup, Inge Li G\u00f8rtz, Esben Bistrup Halvorsen, and Ely Porat. 2016. Distance labeling schemes for trees. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (LIPIcs), Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi (Eds.), Vol. 55. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 132:1\u2013132:16. DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.132"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1105967"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545504"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/3381089.3381116"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840440"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3459637.3482117"},{"key":"e_1_2_1_13_1","volume-title":"Wood","author":"Dujmovi\u0107 Vida","year":"2021","unstructured":"Vida Dujmovi\u0107 , Louis Esperet , Pat Morin , Bartosz Walczak , and David R . Wood . 2021 . Clustered 3-colouring graphs of bounded degree. Combin. Prob. Comput . (2021). https:\/\/doi.org\/10.1017\/S0963548321000213 10.1017\/S0963548321000213 Vida Dujmovi\u0107, Louis Esperet, Pat Morin, Bartosz Walczak, and David R. Wood. 2021. Clustered 3-colouring graphs of bounded degree. Combin. Prob. Comput. (2021). https:\/\/doi.org\/10.1017\/S0963548321000213"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385731"},{"key":"e_1_2_1_15_1","volume-title":"Wood","author":"Dujmovi\u0107 Vida","year":"2019","unstructured":"Vida Dujmovi\u0107 , Pat Morin , and David R . Wood . 2019 . The structure of k-planar graphs. CoRR abs\/1907.05168 (2019). Vida Dujmovi\u0107, Pat Morin, and David R. Wood. 2019. The structure of k-planar graphs. CoRR abs\/1907.05168 (2019)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055349"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1778580.1778634"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-08-00624-3"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060666"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62244"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405049"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2017.06.002"},{"key":"e_1_2_1_23_1","volume-title":"Open Data Structures","author":"Morin Pat","unstructured":"Pat Morin . 2013. Open Data Structures . Athabasca University Press . Retrieved from https:\/\/opendatastructures.org\/. Pat Morin. 2013. Open Data Structures. Athabasca University Press. Retrieved from https:\/\/opendatastructures.org\/."},{"key":"e_1_2_1_24_1","volume-title":"A fast algorithm for the product structure of planar graphs. Algorithmica (Jan","author":"Morin Pat","year":"2021","unstructured":"Pat Morin . 2021. A fast algorithm for the product structure of planar graphs. Algorithmica (Jan . 2021 ). DOI:DOI:https:\/\/doi.org\/10.1007\/s00453-020-00793-5arxiv:2004.02530. 10.1007\/s00453-020-00793-5arxiv:2004.02530 Pat Morin. 2021. A fast algorithm for the product structure of planar graphs. Algorithmica (Jan. 2021). DOI:DOI:https:\/\/doi.org\/10.1007\/s00453-020-00793-5arxiv:2004.02530."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.445"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.01.006"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70644-7"},{"key":"e_1_2_1_29_1","volume-title":"Efficient Graph Representations","author":"Spinrad Jeremy P.","unstructured":"Jeremy P. Spinrad . 2003. Efficient Graph Representations . Fields Institute monographs, Vol. 19 . American Mathematical Society. Retrieved from http:\/\/www.ams.org\/bookstore-getitem\/item=fim-19. Jeremy P. Spinrad. 2003. Efficient Graph Representations. Fields Institute monographs, Vol. 19. American Mathematical Society. Retrieved from http:\/\/www.ams.org\/bookstore-getitem\/item=fim-19."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3477542","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3477542","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:10:37Z","timestamp":1750183837000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3477542"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,5]]},"references-count":28,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3477542"],"URL":"https:\/\/doi.org\/10.1145\/3477542","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,5]]},"assertion":[{"value":"2020-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}