Skip to main content Accessibility help
×
Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-09T17:33:43.344Z Has data issue: false hasContentIssue false

Phase Transitions in Random Planar Graphs

Published online by Cambridge University Press:  06 June 2026

By
Mihyun Kang
Edited by
Andrei Gagarin ,
Roger Behrend ,
Matthew Lettington  and
Iskander Aliev
Andrei Gagarin
Affiliation:
Cardiff University
Roger Behrend
Affiliation:
Cardiff University
Matthew Lettington
Affiliation:
Cardiff University
Iskander Aliev
Affiliation:
Cardiff University
Get access

Summary

We discuss classical results on phase transitions in Erdős–Rényi random graphs and related recent results on random planar graphs and random graphs embeddable on other orientable surfaces of constant genus. The main focus is on how imposing the planarity constraint (or more generally, the genus constraint) a_ects the global and local structure of random graphs, such as their component structure, local limits, and maximum degree.

Information

Type
Chapter
Information
Surveys in Combinatorics 2026 , pp. 1 - 30
Publisher: Cambridge University Press
Print publication year: 2026

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Book purchase

Temporarily unavailable

References

Albenque, Marie, Fusy, Éric, and Lehéricy, Thomas, Random cubic planar graphs converge to the Brownian sphere, Electron. J. Probab. 28 (2023), Paper No. 28, 54 pages.10.1214/23-EJP912CrossRefGoogle Scholar
Aldous, David, Brownian excursions, critical random graphs and the multiplicative coalescent, Ann. Probab. 25 (1997), no. 2, 812–854.Google Scholar
Aldous, David and Michael Steele, J., The objective method: probabilistic combinatorial optimization and local weak convergence, Probability on discrete structures, Encyclopaedia Math. Sci., vol. 110, Springer, Berlin, 2004, pp. 1–72.Google Scholar
Amankwah, Daniel, Björnberg, Jakob, Stefánsson, Sigurdur Ö., Stufler, Benedikt, and Turunen, Joonas, The scaling limit of random 2-connected series-parallel maps, submitted for publication. arXiv: 2503.19705, 2025.Google Scholar
Anastos, Michael, Erde, Joshua, Kang, Mihyun, and Pfenninger, Vincent, A short proof of a central limit theorem for the order of the giant component and k-core, submitted for publication. arXiv: 2506.11651, 2025.Google Scholar
Archdeacon, Dan and Grable, David A., The genus of a random graph, Discrete Math. 142 (1995), no. 1-3, 21–37.Google Scholar
Behrisch, Michael, Coja-Oghlan, Amin, and Kang, Mihyun, The order of the giant component of random hypergraphs, Random Structures Algorithms 36 (2010), no. 2, 149–184.Google Scholar
Behrisch, Michael, Coja-Oghlan, Amin, and Kang, Mihyun, Local limit theorems for the giant component of random hypergraphs, Combin. Probab. Comput. 23 (2014), no. 3, 331–366.Google Scholar
Bender, Edward A. and Gao, Zhicheng, Asymptotic enumeration of labelled graphs by genus, Electron. J. Combin. 18 (2011), no. 1, Paper 13, 28 pages.10.37236/500CrossRefGoogle Scholar
Bender, Edward A., Gao, Zhicheng, and Wormald, Nicholas C., The number of labeled 2-connected planar graphs, Electron. J. Combin. 9 (2002), no. 1, Research Paper 43, 13 pages.10.37236/1659CrossRefGoogle Scholar
Benjamini, Itai and Schramm, Oded, Recurrence of distributional limits of finite planar graphs, Electron. J. Probab. 6 (2001), no. 23, 13 pages.10.1214/EJP.v6-96CrossRefGoogle Scholar
Bernasconi, Nicla, Panagiotou, Konstantinos, and Steger, Angelika, On properties of random dissections and triangulations, Combinatorica 30 (2010), no. 6, 627–654.Google Scholar
Bodirsky, Manuel, Fusy, Éric, Kang, Mihyun, and Vigerske, Stefan, Boltzmann samplers, Pólya theory, and cycle pointing, SIAM J. Comput. 40 (2011), no. 3, 721–769.Google Scholar
Bodirsky, Manuel, Giménez, Omer, Kang, Mihyun, and Noy, Marc, Enumeration and limit laws for series-parallel graphs, European J. Combin. 28 (2007), no. 8, 2091–2105.Google Scholar
Bodirsky, Manuel, Gröpl, Clemens, Johannsen, Daniel, and Kang, Mihyun, A direct decomposition of 3-connected planar graphs, Sém. Lothar. Combin. 54A (2005), Art. B54Ak, 15 pages.Google Scholar
Bodirsky, Manuel, Gröpl, Clemens, and Kang, Mihyun, Sampling unlabeled biconnected planar graphs, Algorithms and computation, Lecture Notes in Comput. Sci., vol. 3827, Springer, Berlin, 2005, pp. 593–603.Google Scholar
Bodirsky, Manuel, Gröpl, Clemens, and Kang, Mihyun, Generating labeled planar graphs uniformly at random, Theoret. Comput. Sci. 379 (2007), no. 3, 377–386.Google Scholar
Bodirsky, Manuel, Gröpl, Clemens, and Kang, Mihyun, Generating unlabeled connected cubic planar graphs uniformly at random, Random Structures Algorithms 32 (2008), no. 2, 157–180.Google Scholar
Bodirsky, Manuel, Kang, Mihyun, Löffler, Mike, and McDiarmid, Colin, Random cubic planar graphs, Random Structures Algorithms 30 (2007), no. 1-2, 78–94.Google Scholar
Bollobás, Béla, The distribution of the maximum degree of a random graph, Discrete Math. 32 (1980), no. 2, 201–203.Google Scholar
Bollobás, Béla, Degree sequences of random graphs, Discrete Math. 33 (1981), no. 1, 1–19.Google Scholar
Bollobás, Béla, Vertices of given degree in a random graph, J. Graph Theory 6 (1982), no. 2, 147–155.Google Scholar
Bollobás, Béla, The evolution of random graphs, Trans. Amer. Math. Soc. 286 (1984), no. 1, 257–274.Google Scholar
Bollobás, Béla, Random graphs, second ed., Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge University Press, Cambridge, 2001.Google Scholar
Bollobás, Béla and Riordan, Oliver, Asymptotic normality of the size of the giant component via a random walk, J. Combin. Theory Ser. B 102 (2012), no. 1, 53–61.Google Scholar
Bouttier, Jérémie, Francesco, Philippe Di, and Guitter, Emmanuel, Planar maps as labeled mobiles, Electron. J. Combin. 11 (2004), no. 1, Research Paper 69, 27 pages.10.37236/1822CrossRefGoogle Scholar
Chapuy, Guillaume, Fusy, Éric, Giménez, Omer, Mohar, Bojan, and Noy, Marc, Asymptotic enumeration and limit laws for graphs of fixed genus, J. Combin. Theory Ser. A 118 (2011), no. 3, 748–777.Google Scholar
Chapuy, Guillaume, Fusy, Éric, Giménez, Omer, and Noy, Marc, On the diameter of random planar graphs, Combin. Probab. Comput. 24 (2015), no. 1, 145–178.Google Scholar
Chapuy, Guillaume, Fusy, Éric, Kang, Mihyun, and Shoilekova, Bilyana, A complete grammar for decomposing a family of graphs into 3-connected components, Electron. J. Combin. 15 (2008), no. 1, Research Paper 148, 39 pages.CrossRefGoogle Scholar
Amin Coja-Oghlan, Oliver Cooley, Kang, Mihyun, and Skubch, Kathrin, How does the core sit inside the mantle?, Random Structures Algorithms 51 (2017), no. 3, 459–482.Google Scholar
Amin Coja-Oghlan, Oliver Cooley, Kang, Mihyun, and Skubch, Kathrin, Core forging and local limit theorems for the k-core of random graphs, J. Combin. Theory Ser. B 137 (2019), 178–231.Google Scholar
Collet, Gwendal, Drmota, Michael, and Klausner, Lukas D., Limit laws of planar maps with prescribed vertex degrees, Combin. Probab. Comput. 28 (2019), no. 4, 519–541.Google Scholar
Dowden, Chris, The evolution of uniform random planar graphs, Electron. J. Combin. 17 (2010), no. 1, Research Paper 7, 20 pages.10.37236/279CrossRefGoogle Scholar
Dowden, Chris, Random planar graphs with bounds on the maximum and minimum degrees, Graphs Combin. 27 (2011), no. 1, 87–107.Google Scholar
Dowden, Chris, Kang, Mihyun, and Krivelevich, Michael, The genus of the Erdős-Rényi random graph and the fragile genus property, Random Structures Algorithms 56 (2020), no. 1, 97–121.Google Scholar
Dowden, Chris, Kang, Mihyun, and Sprüssel, Philipp, The evolution of random graphs on surfaces, SIAM J. Discrete Math. 32 (2018), no. 1, 695–727.Google Scholar
Drmota, Michael, Random trees: an interplay between combinatorics and probability, Springer, Vienna, 2009.CrossRefGoogle Scholar
Drmota, Michael, Fusy, Éric, Kang, Mihyun, Kraus, Veronika, and Rué, Juanjo, Asymptotic study of subcritical graph classes, SIAM J. Discrete Math. 25 (2011), no. 4, 1615–1651.Google Scholar
Drmota, Michael, Giménez, Omer, and Noy, Marc, Degree distribution in random planar graphs, J. Combin. Theory Ser. A 118 (2011), no. 7, 2102–2130.Google Scholar
Drmota, Michael, Giménez, Omer, Noy, Marc, Panagiotou, Konstantinos, and Steger, Angelika, The maximum degree of random planar graphs, Proc. Lond. Math. Soc. (3) 109 (2014), no. 4, 892–920.Google Scholar
Drmota, Michael, Noy, Marc, Requilé, Clément, and Rué, Juanjo, Random cubic planar maps, Electron. J. Combin. 30 (2023), no. 2, Paper No. 2.51, 41 pages.10.37236/11619CrossRefGoogle Scholar
Drmota, Michael, Noy, Marc, and Stufler, Benedikt, Cut vertices in random planar maps, Electron. J. Combin. 30 (2023), Paper No. 3.32, 32 pages.CrossRefGoogle Scholar
Erdős, Paul and Rényi, Alfréd, On random graphs. I, Publ. Math. Debrecen 6 (1959), 290–297.Google Scholar
Erdős, Paul and Rényi, Alfréd, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960), 17–61.Google Scholar
Flajolet, Philippe and Sedgewick, Robert, Analytic combinatorics, Cambridge University Press, Cambridge, 2009.10.1017/CBO9780511801655CrossRefGoogle Scholar
Fountoulakis, Nikolaos and Panagiotou, Konstantinos, 3-connected cores in random planar graphs, Combin. Probab. Comput. 20 (2011), no. 3, 381–412.Google Scholar
Frieze, Alan and Karoński, Michał, Introduction to random graphs, Cambridge University Press, 2015.10.1017/CBO9781316339831CrossRefGoogle Scholar
Fusy, Éric, Uniform random sampling of planar graphs in linear time, Random Structures Algorithms 35 (2009), no. 4, 464–522.Google Scholar
Gerke, Stefanie and McDiarmid, Colin, On the number of edges in random planar graphs, Combin. Probab. Comput. 13 (2004), no. 2, 165–183.Google Scholar
Gerke, Stefanie, McDiarmid, Colin, Steger, Angelika, and Weißl, Andreas, Random planar graphs with n nodes and a fixed number of edges, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2005, pp. 999–1007.Google Scholar
Gerke, Stefanie, McDiarmid, Colin, Steger, Angelika, and Weißl, Andreas, Random planar graphs with given average degree, Combinatorics, complexity, and chance, Oxford Lecture Ser. Math. Appl., vol. 34, Oxford Univ. Press, Oxford, 2007, pp. 83–102.Google Scholar
Gerke, Stefanie, Schlatter, Dirk, Steger, Angelika, and Taraz, Anusch, The random planar graph process, Random Structures Algorithms 32 (2008), no. 2, 236–261.Google Scholar
Giménez, Omer and Noy, Marc, Asymptotic enumeration and limit laws of planar graphs, J. Amer. Math. Soc. 22 (2009), no. 2, 309–329.Google Scholar
Grimmett, Geoffrey R., Random labelled trees and their branching networks, J. Austral. Math. Soc. Ser. A 30 (1980/81), no. 2, 229–237.Google Scholar
Janson, Svante, Knuth, Donald E., Łuczak, Tomasz, and Pittel, Boris, The birth of the giant component, Random Structures Algorithms 4 (1993), no. 3, 231–358, With an introduction by the editors.Google Scholar
Janson, Svante and Luczak, Malwina J., Asymptotic normality of the k-core in random graphs, Ann. Appl. Probab. 18 (2008), no. 3, 1085–1137.Google Scholar
Janson, Svante, Łuczak, Tomasz, and Rucinski, Andrzej, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000.10.1002/9781118032718CrossRefGoogle Scholar
Kang, Mihyun and Loebl, Martin, The enumeration of planar graphs via Wick’s theorem, Adv. Math. 221 (2009), no. 5, 1703–1724.Google Scholar
Kang, Mihyun and Łuczak, Tomasz, Two critical periods in the evolution of random planar graphs, Trans. Amer. Math. Soc. 364 (2012), no. 8, 4239–4265.Google Scholar
Kang, Mihyun and Missethan, Michael, Concentration of maximum degree in random planar graphs, J. Combin. Theory Ser. B 156 (2022), 310–342.Google Scholar
Kang, Mihyun and Missethan, Michael, Longest and shortest cycles in random planar graphs, Random Structures Algorithms 60 (2022), no. 3, 462–505.Google Scholar
Kang, Mihyun and Missethan, Michael, The early evolution of the random graph process in planar graphs and related classes, SIAM J. Discrete Math. 37 (2023), no. 1, 146–162.Google Scholar
Kang, Mihyun and Missethan, Michael, Benjamini-Schramm local weak limit of sparse random planar graphs, submitted for publication. arXiv: 2101.11910, 2025+.Google Scholar
Kang, Mihyun, Moßhammer, Michael, and Sprüssel, Philipp, Phase transitions in graphs on orientable surfaces, Random Structures Algorithms 56 (2020), no. 4, 1117–1170.Google Scholar
Kang, Mihyun and Sprüssel, Philipp, Symmetries of unlabelled planar triangulations, Electron. J. Combin. 25 (2018), no. 1, Paper No. 1.34, 38 pages.10.37236/6188CrossRefGoogle Scholar
Kortchemski, Igor and Marzouk, Cyril, Large deviation local limit theorems and limits of biconditioned planar maps, Ann. Appl. Probab. 33 (2023), no. 5, 3755–3802.Google Scholar
Gall, Jean-François Le, The topological structure of scaling limits of large planar maps, Invent. Math. 169 (2007), no. 3, 621–670.Google Scholar
Gall, Jean-François Le, Large random planar maps and their scaling limits, European Congress of Mathematics, Eur. Math. Soc., Zürich, 2010, pp. 253–276.Google Scholar
Gall, Jean-François Le, The Brownian map: a universal limit for random planar maps, XVIIth International Congress on Mathematical Physics, World Sci. Publ., Hackensack, NJ, 2014, pp. 420–428.Google Scholar
Gall, Jean-François Le and Miermont, Grégory, Scaling limits of random planar maps with large faces, Ann. Probab. 39 (2011), no. 1, 1–69.Google Scholar
Gall, Jean-François Le and Miermont, Grégory, Scaling limits of random trees and planar maps, Probability and statistical physics in two and more dimensions, Clay Math. Proc., vol. 15, Amer. Math. Soc., Providence, RI, 2012, pp. 155–211.Google Scholar
Liskovets, Valery A. and Walsh, Timothy R., Ten steps to counting planar graphs, Congr. Numer. 60 (1987), 269–277.Google Scholar
Łuczak, Tomasz, Component behavior near the critical point of the random graph process, Random Structures Algorithms 1 (1990), no. 3, 287–310.Google Scholar
Łuczak, Tomasz, Pittel, Boris, and Wierman, John C., The structure of a random graph at the point of the phase transition, Trans. Amer. Math. Soc. 341 (1994), no. 2, 721–748.Google Scholar
McDiarmid, Colin, Random graphs on surfaces, J. Combin. Theory Ser. B 98 (2008), no. 4, 778–797.Google Scholar
McDiarmid, Colin and Reed, Bruce, On the maximum degree of a random planar graph, Combin. Probab. Comput. 17 (2008), no. 4, 591–601.Google Scholar
McDiarmid, Colin, Steger, Angelika, and Welsh, Dominic J. A., Random planar graphs, J. Combin. Theory Ser. B 93 (2005), no. 2, 187–205.Google Scholar
Miermont, Grégory, The Brownian map is the scaling limit of uniform random plane quadrangulations, Acta Math. 210 (2013), no. 2, 319–401.Google Scholar
Molloy, Michael, Cores in random hypergraphs and Boolean formulas, Random Structures Algorithms 27 (2005), no. 1, 124–135.Google Scholar
Noy, Marc, Random planar graphs and beyond, Proceedings of the International Congress of Mathematicians—Seoul 2014. Vol. IV, Kyung Moon Sa, Seoul, 2014, pp. 407–430.Google Scholar
Noy, Marc and Ramos, Lander, Random planar maps and graphs with minimum degree two and three, Electron. J. Combin. 25 (2018), no. 4, Paper No. 4.5, 38 pages.10.37236/7640CrossRefGoogle Scholar
Noy, Marc, Ravelomanana, Vlady, and Rué, Juanjo, On the probability of planarity of a random graph near the critical point, Proc. Amer. Math. Soc. 143 (2015), no. 3, 925–936.Google Scholar
Noy, Marc, Requilé, Clément, and Rué, Juanjo, Further results on random cubic planar graphs, Random Structures Algorithms 56 (2020), no. 3, 892–924.Google Scholar
Osthus, Deryk, Prömel, Hans Jürgen, and Taraz, Anusch, On random planar graphs, the number of planar graphs and their triangulations, J. Combin. Theory Ser. B 88 (2003), no. 1, 119–134.Google Scholar
Panagiotou, Konstantinos and Steger, Angelika, Maximal biconnected subgraphs of random planar graphs, ACM Trans. Algorithms 6 (2010), no. 2, Art. 31, 21 pages.10.1145/1721837.1721847CrossRefGoogle Scholar
Panagiotou, Konstantinos and Steger, Angelika, On the degree distribution of random planar graphs, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2011, pp. 1198–1210.Google Scholar
Pittel, Boris, Spencer, Joel, and Wormald, Nicholas, Sudden emergence of a giant k-core in a random graph, J. Combin. Theory Ser. B 67 (1996), no. 1, 111–151.Google Scholar
Pittel, Boris and Wormald, Nicholas C., Counting connected graphs inside-out, J. Combin. Theory Ser. B 93 (2005), no. 2, 127–172.Google Scholar
Poulalhon, Dominique and Schaeffer, Gilles, Optimal coding and sampling of triangulations, Algorithmica 46 (2006), no. 3-4, 505–527.Google Scholar
Riordan, Oliver, The k-core and branching processes, Combin. Probab. Comput. 17 (2008), no. 1, 111–136.Google Scholar
Riordan, Oliver and Selby, Alex, The maximum degree of a random graph, Combin. Probab. Comput. 9 (2000), no. 6, 549–572.Google Scholar
Rödl, Vojtěch and Thomas, Robin, On the genus of a random graph, Random Structures and Algorithms 6 (1995), no. 1, 1–12.Google Scholar
Sato, Cristiane M., On the robustness of random k-cores, European J. Combin. 41 (2014), 163–182.Google Scholar
Schaeffer, Gilles, Conjugaison d’arbres et cartes combinatoires aléatoires, Ph.D. thesis, Bordeaux 1, 1998.Google Scholar
Schaeffer, Gilles, Random sampling of large planar maps and convex polyhedra, Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1999), ACM, New York, 1999, pp. 760–769.Google Scholar
Stepanov, Vadim E., The probability of the connectedness of a random graph Gm (t), Teor. Verojatnost. i Primenen. 15 (1970), 58–67.Google Scholar
Stufler, Benedikt, Local convergence of random planar graphs, J. Eur. Math. Soc. (JEMS) 25 (2023), no. 1, 1–73.Google Scholar
Stufler, Benedikt, The scaling limit of random cubic planar graphs, J. Lond. Math. Soc. (2) 110 (2024), no. 5, Paper No. e70018, 46 pages.10.1112/jlms.70018CrossRefGoogle Scholar
Tutte, William T., A census of planar triangulations, Canad. J. Math. 14 (1962), 21–38.Google Scholar
Tutte, William T., A census of planar maps, Canad. J. Math. 15 (1963), 249–271.Google Scholar
van der Hofstad, Remco, Random graphs and complex networks. Vol. 1, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 43, Cambridge University Press, Cambridge, 2017.Google Scholar
van der Hofstad, Remco, Random graphs and complex networks. Vol. 2, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 54, Cambridge University Press, Cambridge, 2024.Google Scholar

Accessibility standard: WCAG 2.2 A

Why this information is here

This section outlines the accessibility features of this content - including support for screen readers, full keyboard navigation and high-contrast display options. This may not be relevant for you.

Accessibility Information

The PDF of this chapter complies with version 2.2 of the Web Content Accessibility Guidelines (WCAG), offering more comprehensive accessibility measures for a broad range of users and meets the basic (A) level of WCAG compliance, addressing essential accessibility barriers.

Content Navigation

Table of contents navigation
Allows you to navigate directly to chapters, sections, or non‐text items through a linked table of contents, reducing the need for extensive scrolling.
Index navigation
Provides an interactive index, letting you go straight to where a term or subject appears in the text without manual searching.

Reading Order & Textual Equivalents

Single logical reading order
You will encounter all content (including footnotes, captions, etc.) in a clear, sequential flow, making it easier to follow with assistive tools like screen readers.
Short alternative textual descriptions
You get concise descriptions (for images, charts, or media clips), ensuring you do not miss crucial information when visual or audio elements are not accessible.

Save book to Kindle

To save this book to your Kindle, first ensure no-reply@cambridge.org is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×