Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic
Jesse Campion Loth, Kevin Halasz, Tomás Masarík, Bojan Mohar, Robert Sámal
Abstract
A random 2-cell embedding of a connected graph G in some orientable surface is obtained by choosing a random local rotation around each vertex. Under this setup, the number of faces or the genus of the corresponding 2-cell embedding becomes a random variable. Random embeddings of two particular graph classes -those of a bouquet of n loops and those of n parallel edges connecting two vertices -have been extensively studied and are well-understood. However, little is known about more general graphs despite their important connections with central problems in mainstream mathematics and in theoretical physics (see [Lando & Zvonkin, Graphs on surfaces and their applications, Springer 2004]). There are also tight connections with problems in computing (random generation, approximation algorithms). The results of this paper, in particular, explain why Monte Carlo methods (see, e.g., [Gross & Tucker, Local maxima in graded graphs of imbeddings, Ann. NY Acad. Sci 1979] and [Gross & Rieper, Local extrema in genus stratified graphs, JGT 1991]) cannot work for approximating the minimum genus of graphs.
In his breakthrough work ([Stahl, Permutation-partition pairs, JCTB 1991] and a series of other papers), Stahl developed the foundation of "random topological graph theory". Most of his results have been unsurpassed until today. In our work, we analyze the expected number of faces of random embeddings (equivalently, the average genus) of a graph G. It was very recently shown [Campion Loth & Mohar, Expected number of faces in a random embedding of any graph
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Related papers
- On the Computation of Schrijver's KernelsVincent Delecroix, Oscar Fontaine, Francis LazarusSODA 2026
- Killing a vortexDimitrios M. Thilikos, Sebastian WiederrechtFOCS 2022 · 2 citations
- A quasi-polynomial bound for the minimal excluded minors for a surfaceSarah Houdaigoui, Ken-ichi KawarabayashiSODA 2026
- On the edge expansion of random polytopesAsaf Ferber, Michael Krivelevich, Marcelo Sales, Wojciech SamotijSODA 2026 · 2 citations
- Untangling Graphs on SurfacesÉric Colin de Verdière, Vincent Despré, Loïc DuboisSODA 2024
