{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T21:58:52Z","timestamp":1747173532065,"version":"3.40.5"},"reference-count":32,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T00:00:00Z","timestamp":1684108800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We extend the notion of universal graphs to a geometric setting. A geometric graph is <jats:italic>universal<\/jats:italic> for a class <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000135_inline1.png\"\/><jats:tex-math>\n$\\mathcal H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of planar graphs if it contains an embedding, that is, a crossing-free drawing, of every graph in <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000135_inline2.png\"\/><jats:tex-math>\n$\\mathcal H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Our main result is that there exists a geometric graph with <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000135_inline3.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> vertices and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000135_inline4.png\"\/><jats:tex-math>\n$O\\!\\left(n \\log n\\right)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> edges that is universal for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000135_inline5.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-vertex forests; this generalises a well-known result by Chung and Graham, which states that there exists an (abstract) graph with <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000135_inline6.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> vertices and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000135_inline7.png\"\/><jats:tex-math>\n$O\\!\\left(n \\log n\\right)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> edges that contains every <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000135_inline8.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-vertex forest as a subgraph. The upper bound of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000135_inline9.png\"\/><jats:tex-math>\n$O\\!\\left(n \\log n\\right)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> edges cannot be improved, even if more than <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000135_inline10.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> vertices are allowed. We also prove that every <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000135_inline11.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-vertex convex geometric graph that is universal for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000135_inline12.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-vertex outerplanar graphs has a near-quadratic number of edges, namely <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000135_inline13.png\"\/><jats:tex-math>\n$\\Omega _h(n^{2-1\/h})$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, for every positive integer <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000135_inline14.png\"\/><jats:tex-math>\n$h$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>; this almost matches the trivial <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000135_inline15.png\"\/><jats:tex-math>\n$O(n^2)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> upper bound given by the <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000135_inline16.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-vertex complete convex geometric graph. Finally, we prove that there exists an <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000135_inline17.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-vertex convex geometric graph with <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000135_inline18.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> vertices and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000135_inline19.png\"\/><jats:tex-math>\n$O\\!\\left(n \\log n\\right)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> edges that is universal for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000135_inline20.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-vertex caterpillars.<\/jats:p>","DOI":"10.1017\/s0963548323000135","type":"journal-article","created":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T08:53:58Z","timestamp":1684140838000},"page":"742-761","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Universal geometric graphs"],"prefix":"10.1017","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5987-8713","authenticated-orcid":false,"given":"Fabrizio","family":"Frati","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5307-7106","authenticated-orcid":false,"given":"Michael","family":"Hoffmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8769-3190","authenticated-orcid":false,"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2023,5,15]]},"reference":[{"key":"S0963548323000135_ref30","doi-asserted-by":"publisher","DOI":"10.4064\/aa-9-4-331-340"},{"key":"S0963548323000135_ref31","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00529"},{"key":"S0963548323000135_ref32","doi-asserted-by":"publisher","DOI":"10.2307\/1968197"},{"key":"S0963548323000135_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00069-4"},{"key":"S0963548323000135_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-018-0009-x"},{"key":"S0963548323000135_ref19","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-27.2.203"},{"key":"S0963548323000135_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004117000706"},{"key":"S0963548323000135_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s00208-008-0268-6"},{"key":"S0963548323000135_ref22","doi-asserted-by":"publisher","DOI":"10.1145\/3477542"},{"key":"S0963548323000135_ref26","doi-asserted-by":"publisher","DOI":"10.2307\/2323956"},{"key":"S0963548323000135_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009182"},{"key":"S0963548323000135_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0016-8"},{"key":"S0963548323000135_ref17","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00374"},{"key":"S0963548323000135_ref27","unstructured":"[27] Hoffmann, M. and Klemz, B. (2019) Triconnected planar graphs of maximum degree five are subhamiltonian. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, pp. 58:1\u201358:14, Proceedings of the 27th European Symposium on Algorithms, Volume 144 of Leibniz International Proceedings in Informatics (LIPIcs)."},{"key":"S0963548323000135_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2009.03.005"},{"key":"S0963548323000135_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(78)90072-2"},{"key":"S0963548323000135_ref1","unstructured":"[1] Alon, N. and Capalbo, M. R. (2008) Optimal universal graphs with deterministic embedding. In Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, PA, pp. 373--378."},{"key":"S0963548323000135_ref6","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00318"},{"key":"S0963548323000135_ref5","first-page":"21","article-title":"On graphs which contain all sparse graphs","volume":"12","author":"Babai","year":"1982","journal-title":"Ann. Discrete Math."},{"key":"S0963548323000135_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s004930200017"},{"key":"S0963548323000135_ref11","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.27"},{"key":"S0963548323000135_ref23","unstructured":"[23] Esperet, L. , Joret, G. B. and Morin, P. (2020) Sparse universal graphs for planarity. CoRR, abs\/2010.05779."},{"key":"S0963548323000135_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-011-0029-1"},{"key":"S0963548323000135_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2009.10.010"},{"key":"S0963548323000135_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2014.12.005"},{"key":"S0963548323000135_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.06.009"},{"key":"S0963548323000135_ref2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892007"},{"key":"S0963548323000135_ref9","doi-asserted-by":"publisher","DOI":"10.1137\/0402014"},{"key":"S0963548323000135_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122694"},{"key":"S0963548323000135_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.04.002"},{"key":"S0963548323000135_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(79)90021-2"},{"key":"S0963548323000135_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2019.08.001"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548323000135","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T12:49:50Z","timestamp":1691498990000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548323000135\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,15]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["S0963548323000135"],"URL":"https:\/\/doi.org\/10.1017\/s0963548323000135","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2023,5,15]]},"assertion":[{"value":"\u00a9 The Author(s), 2023. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}