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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A random 2-cell embedding of a given graph $G$ is obtained by choosing arandom local rotation around every vertex. We analyze the expected number offaces of such an embedding, which is equivalent to studying its average genus.In 1991, Stahl proved that the expected number of faces in a random embeddingof an arbitrary graph of order $n$ is at most $n\log(n)$. While there are manyfamilies of graphs whose expected number of faces is $\Theta(n)$, none areknown where the expected number would be super-linear. This lead to theconjecture that there is a linear upper bound. In this note we confirm theconjecture by proving that for any $n$-vertex multigraph, the expected numberof faces in a random 2-cell embedding is at most $n(1+H_m)$, where $m$ is themaximum edge-multiplicity and $H_m$ denotes the $m$th harmonic number. Thisbound is best possible up to a constant factor.

Expected number of faces in a random embedding of any graph is at most linear