{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T18:28:52Z","timestamp":1775845732806,"version":"3.50.1"},"reference-count":92,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,8,17]],"date-time":"2017-08-17T00:00:00Z","timestamp":1502928000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Algorithms, and Data Structures"},{"name":"Mikkel Thorup\u2019s Advanced","award":["DFF-0602-02499B"],"award-info":[{"award-number":["DFF-0602-02499B"]}]},{"name":"Danish Council for Independent Research under the Sapere Aude research career programme"},{"name":"FNU project AlgoDisc--Discrete Mathematics"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,8,31]]},"abstract":"<jats:p>\n            In this article, we show that there exists a graph\n            <jats:italic>G<\/jats:italic>\n            with\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) nodes such that any forest of\n            <jats:italic>n<\/jats:italic>\n            nodes is an induced subgraph of\n            <jats:italic>G<\/jats:italic>\n            . Furthermore, for constant arboricity\n            <jats:italic>k<\/jats:italic>\n            , the result implies the existence of a graph with\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            ) nodes that contains all\n            <jats:italic>n<\/jats:italic>\n            -node graphs of arboricity\n            <jats:italic>k<\/jats:italic>\n            as node-induced subgraphs, matching a\n            <jats:italic>\u03a9<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            ) lower bound of Alstrup and Rauhe. Our upper bounds are obtained through a log\n            <jats:sub>2<\/jats:sub>\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>O<\/jats:italic>\n            (1) labeling scheme for adjacency queries in forests.\n          <\/jats:p>\n          <jats:p>We hereby solve an open problem being raised repeatedly over decades by authors such as Kannan et al., Chung, and Fraigniaud and Korman.<\/jats:p>","DOI":"10.1145\/3088513","type":"journal-article","created":{"date-parts":[[2017,8,24]],"date-time":"2017-08-24T11:49:04Z","timestamp":1503575344000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Optimal Induced Universal Graphs and Adjacency Labeling for Trees"],"prefix":"10.1145","volume":"64","author":[{"given":"Stephen","family":"Alstrup","sequence":"first","affiliation":[{"name":"University of Copenhagen, Denmark"}]},{"given":"S\u00f8ren","family":"Dahlgaard","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Denmark"}]},{"given":"Mathias B\u00e6k Tejs","family":"Knudsen","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Denmark"}]}],"member":"320","published-online":{"date-parts":[[2017,8,17]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 57th IEEE Symposium on Foundations of Computer Science (FOCS\u201916)","author":"Abboud A."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703437211"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 12th ACM\/SIAM Symposium on Discrete Algorithms (SODA\u201901)","author":"Abiteboul S."},{"key":"e_1_2_1_4_1","unstructured":"M. Abrahamsen S. Alstrup J. Holm M. B. T. Knudsen and M. Stockel. 2016. Near-Optimal Induced Universal Graphs for Bounded Degree Graphs. arXiv:1607.04911.  M. Abrahamsen S. Alstrup J. Holm M. B. T. Knudsen and M. Stockel. 2016. Near-Optimal Induced Universal Graphs for Bounded Degree Graphs. arXiv:1607.04911."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP\u201914)","author":"Adjiashvili D."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-017-0396-9"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1286320.1286324"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 19th ACM\/SIAM Symposium on Discrete Algorithms (SODA\u201908)","author":"Alon N."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 28th ACM\/SIAM Symposium on Discrete Algorithms (SODA\u201917)","author":"Alon N."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103433409"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 24th European Symposium on Algorithms (ESA\u201916)","author":"Alstrup S."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 27th ACM\/SIAM Symposium on Discrete Algorithms (SODA\u201916)","author":"Alstrup S."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746545"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 13th ACM\/SIAM Symposium on Discrete Algorithms (SODA\u201902)","author":"Alstrup S."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS\u201902)","author":"Alstrup S."},{"key":"e_1_2_1_16_1","first-page":"21","article-title":"On graphs which contain all sparse graphs","volume":"12","author":"Babai L.","year":"1982","journal-title":"Annals Discrete Mathematics"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.12.091"},{"key":"e_1_2_1_18_1","volume-title":"Recent Advances in Graph Theory: Proceedings of the Prague Symposium. 31--48","author":"Beineke L. W."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.38"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0402014"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(81)80015-7"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(71)90016-5"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/11780823_12"},{"key":"e_1_2_1_24_1","unstructured":"N. Bonichon C. Gavoille and A. Labourel. 2007a. An efficient adjacency scheme for bounded degree trees. Preprint version.  N. Bonichon C. Gavoille and A. Labourel. 2007a. An efficient adjacency scheme for bounded degree trees. Preprint version."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2007.01.022"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1966.1053860"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(67)90082-0"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-009-0860-x"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760181"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.07.011"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190140408"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(78)90072-2"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1749-6632.1979.tb32784.x"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-27.2.203"},{"key":"e_1_2_1_35_1","unstructured":"F. R. K. Chung R. L. Graham and D. Coppersmith. 1981. On trees which contain all small trees. In The Theory and Applications of Graphs. John Wiley & Sons 265--272.  F. R. K. Chung R. L. Graham and D. Coppersmith. 1981. On trees which contain all small trees. In The Theory and Applications of Graphs. John Wiley & Sons 265--272."},{"key":"e_1_2_1_36_1","first-page":"213","article-title":"On graphs which contain all small trees II","volume":"18","author":"Chung F. R. K.","year":"1976","journal-title":"Colloquia Mathematica"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958016.1958030"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1134"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_45"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806771"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00002-6"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055349"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.04.020"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.09.031"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9664-0"},{"key":"e_1_2_1_46_1","first-page":"133","article-title":"Minimum graphs that contain all small trees","volume":"25","author":"Fishburn P. C.","year":"1985","journal-title":"Ars Combinatoria"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 28th International Colloquium on Automata, Languages, and Programming (ICALP\u201901)","author":"Fraigniaud P."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584031"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the 21st ACM\/SIAM Symposium on Discrete Algorithms (SODA\u201910)","author":"Fraigniaud P."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2794076"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579202"},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the Workshop on Advances in Distributed Graph Algorithms (ADGA\u201912)","author":"Gavoille C.","year":"2012"},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of the 15th European Symposium on Algorithms (ESA\u201907)","author":"Gavoille C."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/050635006"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-002-0073-5"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.05.002"},{"key":"e_1_2_1_57_1","volume-title":"Graph Theory and Applications. Lecture Notes in Computer Science","volume":"303","author":"Graham R. L."},{"key":"e_1_2_1_58_1","volume-title":"Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (FOCS\u201903)","author":"Gupta A."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702409927"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830000122X"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405049"},{"key":"e_1_2_1_62_1","volume-title":"Proceedings of the 7th Workshop on Algorithms and Data Structures (WADS\u201901)","author":"Kaplan H."},{"key":"e_1_2_1_63_1","volume-title":"Proceedings of the 13th ACM\/SIAM Symposium on Discrete Algorithms (SODA\u201902)","author":"Kaplan H."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703433912"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721855"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2007.08.004"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.9"},{"key":"e_1_2_1_68_1","first-page":"237","article-title":"On decomposition of graphs","volume":"1","author":"Lovasz L.","year":"1966","journal-title":"Studia Scientiarum Mathematicarum Hungarica"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1515\/dma.1997.7.3.295"},{"key":"e_1_2_1_70_1","first-page":"345","article-title":"Minimal universal bipartite graphs","volume":"84","author":"Lozin V. V.","year":"2007","journal-title":"Ars Combinatoria"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1017\/S2040618500035139"},{"key":"e_1_2_1_72_1","unstructured":"J. W. Moon. 1968. Topics on Tournaments. Holt Rinehart & Winston.  J. W. Moon. 1968. Topics on Tournaments. Holt Rinehart & Winston."},{"key":"e_1_2_1_73_1","unstructured":"J. H. M\u00fcller. 1988. Local Structure in Graph Classes. Ph.D. Dissertation. Georgia Institute of Technology.  J. H. M\u00fcller. 1988. Local Structure in Graph Classes. Ph.D. Dissertation. Georgia Institute of Technology."},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.005"},{"key":"e_1_2_1_75_1","volume-title":"Proceedings of the 38th IEEE Symposium on Foundations of Computer Science (FOCS\u201997)","author":"Munro J. I."},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.21136\/CPM.1975.117886"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190120204"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.83"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.5555\/1379811.1379818"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.03.015"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90172-6"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.4064\/aa-9-4-331-340"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/28.1.5"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1027"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_2_1_86_1","volume-title":"Fields Institute Monographs","volume":"19","author":"Spinrad J. P.","year":"2003"},{"key":"e_1_2_1_87_1","unstructured":"A. Takahashi and S. Ueno Y. Kajitani. 1995. Universal graphs for graphs with bounded path-width. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences E78--A 4 458--462.  A. Takahashi and S. Ueno Y. Kajitani. 1995. Universal graphs for graphs with bounded path-width. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences E78--A 4 458--462."},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007399"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039493"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"e_1_2_1_91_1","unstructured":"Wikipedia. 2013. Implicit Graph. Retrieved June 2 2017 from http:\/\/en.wikipedia.org\/w\/index.php?title&equals;Implicit_graph8oldid&equals;585232203  Wikipedia. 2013. Implicit Graph. Retrieved June 2 2017 from http:\/\/en.wikipedia.org\/w\/index.php?title&equals;Implicit_graph8oldid&equals;585232203"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579350"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3088513","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3088513","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:07Z","timestamp":1750217407000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3088513"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,17]]},"references-count":92,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,8,31]]}},"alternative-id":["10.1145\/3088513"],"URL":"https:\/\/doi.org\/10.1145\/3088513","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,17]]},"assertion":[{"value":"2016-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}