{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T15:21:22Z","timestamp":1771600882384,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":27,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANR Projects GrR","award":["ANR-18-CE40-0032"],"award-info":[{"award-number":["ANR-18-CE40-0032"]}]},{"name":"ANR Projects DISTANCIA","award":["ANR-17-CE40-0015"],"award-info":[{"award-number":["ANR-17-CE40-0015"]}]},{"name":"LabEx PERSYVAL-lab","award":["ANR-11-LABX-0025"],"award-info":[{"award-number":["ANR-11-LABX-0025"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451102","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"1109-1117","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Optimal labelling schemes for adjacency, comparability, and reachability"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7905-8018","authenticated-orcid":false,"given":"Marthe","family":"Bonamy","sequence":"first","affiliation":[{"name":"CNRS, France \/ Labri, France \/ University of Bordeaux, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6200-0514","authenticated-orcid":false,"given":"Louis","family":"Esperet","sequence":"additional","affiliation":[{"name":"CNRS, France \/ G-SCOP, France \/ Grenoble Alps University, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9878-8750","authenticated-orcid":false,"given":"Carla","family":"Groenland","sequence":"additional","affiliation":[{"name":"University of Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4489-5988","authenticated-orcid":false,"given":"Alex","family":"Scott","sequence":"additional","affiliation":[{"name":"University of Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"On the entropy values of hereditary classes of graphs. Discrete Mathematics and Applications, \\bfseries 3(2):191\u2013200","author":"Alekseev V.","year":"1993","unstructured":"V. Alekseev. On the entropy values of hereditary classes of graphs. Discrete Mathematics and Applications, \\bfseries 3(2):191\u2013200, 1993."},{"key":"e_1_3_2_1_2_1","volume-title":"Asymptotically optimal induced universal graphs. Geometric and Functional Analysis, \\bfseries 27(1):1\u201332","author":"Alon N.","year":"2017","unstructured":"N. Alon. Asymptotically optimal induced universal graphs. Geometric and Functional Analysis, \\bfseries 27(1):1\u201332, 2017."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2010.10.001"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1005"},{"key":"e_1_3_2_1_5_1","volume-title":"Colorings and orientations of graphs. Combinatorica, \\bfseries 12(2):125\u2013134","author":"Alon N.","year":"1992","unstructured":"N. Alon and M. Tarsi. Colorings and orientations of graphs. Combinatorica, \\bfseries 12(2):125\u2013134, 1992."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746545"},{"key":"e_1_3_2_1_7_1","volume-title":"Implicit representations and factorial properties of graphs. Discrete Mathematics, \\bfseries 338(2):164\u2013179","author":"Atminas A.","year":"2015","unstructured":"A. Atminas, A. Collins, V. Lozin and V. Zamaraev. Implicit representations and factorial properties of graphs. Discrete Mathematics, \\bfseries 338(2):164\u2013179, 2015."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.2000.0476"},{"key":"e_1_3_2_1_9_1","volume-title":"Projections of bodies and hereditary properties of hypergraphs. Bulletin of the London Mathematical Society, \\bfseries 27(5):417\u2013424","author":"Bollob\u00e1s B.","year":"1995","unstructured":"B. Bollob\u00e1s and A. Thomason. Projections of bodies and hereditary properties of hypergraphs. Bulletin of the London Mathematical Society, \\bfseries 27(5):417\u2013424, 1995."},{"key":"e_1_3_2_1_10_1","first-page":"78","volume-title":"The Mathematics of Paul Erd\u00f6s II","author":"Bollob\u00e1s B.","unstructured":"B. Bollob\u00e1s and A. Thomason. Hereditary and monotone properties of graphs. In The Mathematics of Paul Erd\u00f6s II, pages 70\u201378. Springer, 1997."},{"key":"e_1_3_2_1_11_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10\u201313, 2021, 2021","author":"Bonnet E.","year":"2006","unstructured":"E. Bonnet, C. Geniet, E. J. Kim, S. Thomass\u00e9 and R. Watrigant. Twin-width II: small classes. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10\u201313, 2021, 2021. https:\/\/arxiv.org\/abs\/2006.09877."},{"issue":"5","key":"e_1_3_2_1_12_1","first-page":"1627","volume":"28","author":"Brodnik A.","year":"1999","unstructured":"A. Brodnik and J. I. Munro. Membership in constant time and almost-minimum space. SIAM Journal on computing, \\bfseries 28(5):1627\u20131640, 1999.","journal-title":"Membership in constant time and almost-minimum space. SIAM Journal on computing, \\bfseries"},{"key":"e_1_3_2_1_13_1","volume-title":"Proceedings of the 61th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Virtual Conference, November 16\u201319, 2020, 2020","author":"Dujmovi\u0107 V.","year":"2003","unstructured":"V. Dujmovi\u0107, L. Esperet, C. Gavoille, G. Joret, P. Micek and P. Morin. Adjacency labelling for planar graphs (and beyond). In Proceedings of the 61th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Virtual Conference, November 16\u201319, 2020, 2020. https:\/\/arxiv.org\/abs\/2003.04280."},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020)","author":"M.","year":"2020","unstructured":"M. Dul\\keba, P. Gawrychowski and W. Janczewski. Efficient labeling for reachability in digraphs. In Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020), 2020."},{"key":"e_1_3_2_1_15_1","volume-title":"Boolean dimension and tree-width. Combinatorica, \\bfseries 40(5):655\u2013677","author":"Felsner S.","year":"2020","unstructured":"S. Felsner, T. M\u00e9sz\u00e1ros and P. Micek. Boolean dimension and tree-width. Combinatorica, \\bfseries 40(5):655\u2013677, 2020."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100217"},{"key":"e_1_3_2_1_18_1","volume-title":"MathOverflow","author":"Hamkins J. D.","year":"2010","unstructured":"J. D. Hamkins. What is the minimal size of a partial order that is universal for all partial orders of size $n$? MathOverflow, 2010. https:\/\/mathoverflow.net\/q\/25874."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62244"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405049"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1970-0253944-9"},{"key":"e_1_3_2_1_22_1","volume-title":"Proceedings of the Glasgow Mathematical Association, \\bfseries 7(1):32\u201333","author":"Moon J. W.","year":"1965","unstructured":"J. W. Moon. On minimal $n$-universal graphs. Proceedings of the Glasgow Mathematical Association, \\bfseries 7(1):32\u201333, 1965."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0047-1"},{"key":"e_1_3_2_1_25_1","series-title":"SIAM Journal on Computing, \\bfseries 31(2):353\u2013363","volume-title":"Low redundancy in static dictionaries with constant query time","author":"Pagh R.","year":"2001","unstructured":"R. Pagh. Low redundancy in static dictionaries with constant query time. SIAM Journal on Computing, \\bfseries 31(2):353\u2013363, 2001."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1090\/fim\/019"},{"key":"e_1_3_2_1_27_1","volume-title":"Compact oracles for reachability and approximate distances in planar digraphs. J. ACM, \\bfseries 51(6):993\u20131024","author":"Thorup M.","year":"2004","unstructured":"M. Thorup. Compact oracles for reachability and approximate distances in planar digraphs. J. ACM, \\bfseries 51(6):993\u20131024, 2004."},{"key":"e_1_3_2_1_28_1","volume-title":"On an extremal problem in graph theory. Matematikai \u00e9s Fizikai Lapok, \\bfseries 48:436\u2013452","author":"Tur\u00e1n P.","year":"1941","unstructured":"P. Tur\u00e1n. On an extremal problem in graph theory. Matematikai \u00e9s Fizikai Lapok, \\bfseries 48:436\u2013452, 1941."}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451102","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":27,"alternative-id":["10.1145\/3406325.3451102","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451102","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}