English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

A random 2-cell embedding of a connected graph $G$ in some orientable surfaceis obtained by choosing a random local rotation around each vertex. Under thissetup, the number of faces or the genus of the corresponding 2-cell embeddingbecomes a random variable. Random embeddings of two particular graph classes,those of a bouquet of $n$ loops and those of $n$ parallel edges connecting twovertices, have been extensively studied and are well-understood. However,little is known about more general graphs. The results of this paper explainwhy Monte Carlo methods cannot work for approximating the minimum genus ofgraphs.  In his breakthrough work [Permutation-partition pairs, JCTB 1991], Stahldeveloped the foundation of "random topological graph theory". Most of hisresults have been unsurpassed until today. In our work, we analyze the expectednumber of faces of random embeddings (equivalently, the average genus) of agraph $G$. It was very recently shown that for any graph $G$, the expectednumber of faces is at most linear. We show that the actual expected number offaces $F(G)$ is almost always much smaller. In particular, we prove:  1) $\frac{1}{2}\ln n - 2 < \mathbb{E}[F(K_n)] \le 3.65 \ln n +o(1)$.  2) For random graphs $G(n,p)$ ($p=p(n)$), we have $\mathbb{E}[F(G(n,p))] \le\ln^2 n+\frac{1}{p}$.  3) For random models $B(n,\Delta)$ containing only graphs, whose maximumdegree is at most $\Delta$, we get stronger bounds$\mathbb{E}[F(B(n,\Delta))]=\Theta(\ln n)$.

Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic