{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:46:20Z","timestamp":1787319980857,"version":"build-2736575974"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P27290"],"award-info":[{"award-number":["P27290"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>For integers $g,m \\geq 0$ and $n&gt;0$, let $S_{g}(n,m)$ denote the graph taken uniformly at random from the set of all graphs on $\\{1,2, \\ldots, n\\}$ with exactly $m=m(n)$ edges and with genus at most $g$. We use counting arguments to investigate the components, subgraphs, maximum degree, and largest face size of $S_{g}(n,m)$, finding that there is often different asymptotic behavior depending on the ratio $\\frac{m}{n}$. In our main results, we show that the probability that $S_{g}(n,m)$ contains any given nonplanar component converges to 0 as $n \\to \\infty$ for all $m(n)$, the probability that $S_{g}(n,m)$ contains a copy of any given planar graph converges to 1 as $n \\to \\infty$ if $\\liminf \\frac{m}{n} &gt; 1$, the maximum degree of $S_{g}(n,m)$ is $\\Theta (\\ln n)$ with high probability if $\\liminf \\frac{m}{n} &gt; 1$, and the largest face size of $S_{g}(n,m)$ has a threshold around $\\frac{m}{n}=1$, where it changes from $\\Theta (n)$ to $\\Theta (\\ln n)$ with high probability.<\/jats:p>","DOI":"10.1137\/17m113383x","type":"journal-article","created":{"date-parts":[[2018,3,27]],"date-time":"2018-03-27T12:33:35Z","timestamp":1522154015000},"page":"695-727","source":"Crossref","is-referenced-by-count":5,"title":["The Evolution of Random Graphs on Surfaces"],"prefix":"10.1137","volume":"32","author":[{"given":"Chris","family":"Dowden","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mihyun","family":"Kang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Philipp","family":"Spr\u00fcssel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,3,27]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000272"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.09.003"},{"key":"atypb3","doi-asserted-by":"crossref","first-page":"43","DOI":"10.37236\/1659","volume":"9","author":"Bender E.","year":"2002","journal-title":"Electron. J. Combin."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.045"},{"key":"atypb5","unstructured":"B. Bolloba\u0301s,\n                      Random Graphs\n                      , Cambridge University Press, Cambridge, 2001."},{"key":"atypb6","first-page":"323","volume":"58","author":"Brinkmann G.","year":"2007","journal-title":"MATCH Commun. Math. Comput. Chem."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2010.11.014"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548314000467"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"G. Chapuy and G. Perarnau,\n                      Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture\n                      , in Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'16), 2016, pp. 1580-1588.","DOI":"10.1137\/1.9781611974331.ch107"},{"key":"atypb10","unstructured":"C. Dowden,\n                      Uniform Random Planar Graphs with Degree Constraints\n                      , D.Phil. thesis, Oxford University, 2008; available online fromhttps:\/\/ora.ouls.ox.ac.uk."},{"key":"atypb11","doi-asserted-by":"crossref","first-page":"7","DOI":"10.37236\/279","volume":"17","author":"Dowden C.","year":"2010","journal-title":"Electron. J. Combin."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/pdu024"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2011.04.010"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9751-x"},{"key":"atypb15","first-page":"464","volume":"35","year":"2009","journal-title":"Algorithms"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480195292053"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1999.3006"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548303005947"},{"key":"atypb19","unstructured":"S. Gerke, C. McDiarmid, A. Steger, and A. Wei\u00dfl,\n                      Random planar graphs with n nodes and a fixed number of edges\n                      , in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'05), 2005, pp. 999-1007."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-08-00624-3"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"S. Janson, T. \u0141uczak, and A. Rucin\u0301ski,\n                      Random Graphs\n                      , Wiley, New York, 2000.","DOI":"10.1002\/9781118032718"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2012-05502-4"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2017.07.024"},{"key":"atypb24","unstructured":"M. Kang, M. Mo\u00dfhammer, and P. Spru\u0308ssel,\n                      Phase Transitions in Graphs on Orientable Surfaces\n                      , preprint,arXiv:1708.07671."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.12.001"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.11.006"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009097"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.09.007"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"C. McDiarmid, A. Steger, and D. Welsh,\n                      Random graphs from planar and other addable classes\n                      , in Topics in Discrete Mathematics, pp. 231-246, Springer, Berlin, 2006.","DOI":"10.1007\/3-540-33700-8_15"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M113383X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:54:22Z","timestamp":1787316862000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M113383X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M113383X"],"URL":"https:\/\/doi.org\/10.1137\/17m113383x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}