{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T08:51:16Z","timestamp":1791276676516,"version":"4.1.0"},"reference-count":72,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-21-CE48-0014-01"],"award-info":[{"award-number":["ANR-21-CE48-0014-01"]}],"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-24-CE48-7768"],"award-info":[{"award-number":["ANR-24-CE48-7768"]}],"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-11-LABX-0025"],"award-info":[{"award-number":["ANR-11-LABX-0025"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["VI.Veni.232.073"],"award-info":[{"award-number":["VI.Veni.232.073"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["J1-4008"],"award-info":[{"award-number":["J1-4008"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-19-CE48-0013"],"award-info":[{"award-number":["ANR-19-CE48-0013"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["EXC-2046\/1"],"award-info":[{"award-number":["EXC-2046\/1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["390685689"],"award-info":[{"award-number":["390685689"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2026,12,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>It was proved by Huynh et al. [ Universality in Minor-Closed Graph Classes, preprint, arXiv:2109.00327,\u00a02021]\u00a0that any countable graph containing every countable planar graph as a subgraph has an infinite clique minor. We prove a finite, quantitative version of this result: for fixed [Formula: see text], if a graph [Formula: see text] is [Formula: see text]-minor-free and contains every [Formula: see text]-vertex planar graph as a subgraph, then [Formula: see text] has [Formula: see text] vertices. On the other hand, we construct a polynomial size [Formula: see text]-minor-free graph containing every [Formula: see text]-vertex tree as an induced subgraph, and a polynomial size [Formula: see text]-minor-free graph containing every [Formula: see text]-vertex [Formula: see text]-minor-free graph as the induced subgraph. This answers several problems raised recently by Bergold et al. [ Subgraph-universal planar graphs for trees, in Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci., Springer, 2025, pp. 62\u201375]. We study more generally the order of universal graphs for various classes (of graphs of bounded degree, treedepth, pathwidth, or treewidth) if the universal graphs retain some of the structure of the original class.<\/jats:p>","DOI":"10.1137\/25m1760799","type":"journal-article","created":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T08:00:26Z","timestamp":1791273626000},"page":"1727-1761","source":"Crossref","is-referenced-by-count":0,"title":["Faithful Universal Graphs for Minor-Closed Classes"],"prefix":"10.1137","volume":"40","author":[{"given":"Paul","family":"Bastide","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Bordeaux, LaBRI, 33405 Bordeaux, France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6200-0514","authenticated-orcid":true,"given":"Louis","family":"Esperet","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Grenoble Alpes, CNRS, Laboratoire G-SCOP, 38000 Grenoble, France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9878-8750","authenticated-orcid":true,"given":"Carla","family":"Groenland","sequence":"additional","affiliation":[{"name":"Delft Institute of Applied Mathematics, Technische Universiteit, 2628 Delft, The Netherlands."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Claire","family":"Hilaire","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Clermont Auvergne, Clermont Auvergne INP, LIMOS, 63001 Clermont-Ferrand, France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-0706-3477","authenticated-orcid":true,"given":"Cl\u00e9ment","family":"Rambaud","sequence":"additional","affiliation":[{"name":"Universit\u00e9 C\u00f4te d\u2019Azur, I3S, Inria, CNRS, 06900 Sophia-Antipolis, France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4841-5937","authenticated-orcid":true,"given":"Alexandra","family":"Wesolek","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, 10623 Berlin, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,10,6]]},"reference":[{"key":"ref1","first-page":"128:1","volume-title":"44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, LIPIcs 80","author":"Abrahamsen M.","year":"2017"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20143"},{"key":"ref3","unstructured":"N. Alon and M. Capalbo, Optimal universal graphs with deterministic embedding, in Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201908, SIAM, 2008, pp. 373\u2013378."},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01594179"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44666-4_20"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1145\/3088513"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1137\/16M1105967"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-017-0396-9"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004117000706"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73486-8"},{"key":"ref11","series-title":"Lecture Notes in Comput. Sci.","first-page":"62","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Bergold H.","year":"2025"},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"S. N. Bhatt, F. R. K. Chung, F. T. Leighton, and A. L. Rosenberg, Optimal simulations of tree machines (preliminary version), in Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science, 1986, pp. 274\u2013282.","DOI":"10.1109\/SFCS.1986.38"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1137\/0402014"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2025.115643"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1137\/20M1330464"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0055821"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"S. N. Bhatt and C. E. Leiserson, How to assemble tree machines (extended abstract), in Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, STOC \u201982, 1982, pp. 77\u201384.","DOI":"10.1145\/800070.802179"},{"key":"ref18","volume":"20","author":"Bonnet \u00c9.","year":"2024","journal-title":"Log. Methods Comput. Sci."},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80030-8"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-26.2.201"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/bdu059"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60406-5_32"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-8268-2_15"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1007\/s004930200017"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-27.2.203"},{"key":"ref26","first-page":"265","author":"Chung F. R. K.","year":"1981","journal-title":"in The Theory of Applications of Graphs"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(81)90037-X"},{"key":"ref28","first-page":"17","volume-title":"Paths, Flows, and VLSI-Layout, Algorithms Combin. 9","author":"Chung F. R. K.","year":"1990"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190140408"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1137\/0604055"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.2307\/2695110"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.05.008"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-3181-5"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1006\/aama.1998.0641"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20245"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1145\/3477542"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579242"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(85)80008-1"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1112\/jlms.12781"},{"key":"ref40","doi-asserted-by":"crossref","unstructured":"M. Elberfeld, A. Jakoby, and T. Tantau, Logspace versions of the theorems of Bodlaender and Courcelle, in Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, 2010, pp. 143\u2013152.","DOI":"10.1109\/FOCS.2010.21"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1007\/BF01895716"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548323000135"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200905"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199705)25:1<53::AID-JGT3>3.0.CO;2-H"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977066.3"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1007\/BF01116454"},{"key":"ref47","doi-asserted-by":"crossref","unstructured":"C. Gavoille and A. Labourel, Shorter implicit representation for planar graphs and bounded treewidth graphs, in Algorithms \u2013 ESA 2007, 15th Annual European Symposium, Eilat, Israel, Proceedings, 2007, pp. 582\u2013593.","DOI":"10.1007\/978-3-540-75520-3_52"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1971.38.69"},{"key":"ref49","doi-asserted-by":"crossref","unstructured":"H. Hatami and P. Hatami, The implicit graph conjecture is false, in Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS \u201922), 2022, pp. 1134\u20131137.","DOI":"10.1109\/FOCS54457.2022.00109"},{"key":"ref50","unstructured":"T. Huynh, B. Mohar, R. \u0160\u00e1mal, C. Thomassen, and D. R. Wood, Universality in Minor-Closed Graph Classes, preprint\n                      ,\n                      arXiv:2109.00327, 2021."},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(66)80060-1"},{"key":"ref52","unstructured":"K. Hendrey and D. R. Wood, Short Paths in the Planar Graph Product Structure Theorem, preprint, arXiv:2502.01927, 2025."},{"key":"ref53","doi-asserted-by":"crossref","unstructured":"P. Hrube\u0161, A. Wigderson, and A. Yehudayoff, Relationless completeness and separations, in Proceedings of the 25th Annual IEEE Conference on Computational Complexity (CCC \u201910), Cambridge, MA, 2010, pp. 280\u2013290.","DOI":"10.1109\/CCC.2010.34"},{"key":"ref54","unstructured":"N. Kaul, J. Kim, M. Kim, and D. R. Wood, On Universal Graphs for Trees and Tree-Like Graphs, preprint\n                      ,\n                      arXiv:2511.22358, 2026."},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1007\/BF02787220"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1137\/0405049"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00339-2"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579141"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1112\/S002557930001250X"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2017.09.006"},{"key":"ref61","unstructured":"J. H. Muller, Local Structure in Graph Classes, Ph.D. thesis, School of Information and Computer Science, 1988."},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(81)80043-1"},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.4064\/aa-9-4-331-340"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(72)90019-2"},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(80)90158-2"},{"key":"ref66","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1972.41.247"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1090\/fim\/019"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139871495"},{"key":"ref69","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80039-4"},{"key":"ref70","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100061521"},{"key":"ref71","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.6312176"},{"key":"ref72","doi-asserted-by":"publisher","DOI":"10.1137\/0114062"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/25M1760799","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T08:00:31Z","timestamp":1791273631000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/25M1760799"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,10,6]]},"references-count":72,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,12,31]]}},"alternative-id":["10.1137\/25M1760799"],"URL":"https:\/\/doi.org\/10.1137\/25m1760799","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,10,6]]}}}