Random 2-cell embeddings of multistars

Abstract

Random 2-cell embeddings of a given graph $G$ are obtained by choosing a random local rotation around every vertex. We analyze the expected number of faces, $\mathbb{E}[F_G]$, of such an embedding which is equivalent to studying its average genus. So far, tight results are known for two families called monopoles and dipoles. We extend the dipole result to a more general family called multistars, i.e., loopless multigraphs in which there is a vertex incident with all the edges. In particular, we show that the expected number of faces of every multistar with $n$ nonleaf edges lies in an interval of length $2/(n+1)$ centered at the expected number of faces of an $n$-edge dipole. This allows us to derive bounds on $\mathbb{E}[F_G]$ for any given graph $G$ in terms of vertex degrees. We conjecture that $\mathbb{E}[F_G]\le O(n)$ for any simple $n$-vertex graph $G$.

15 pages, 2 figures. Accepted to European conference on combinatorics, graph theory and applications (EUROCOMB) 2021

Cited by in corpus (1)

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