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, E[FG], 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 E[FG] for any given graph G in terms of vertex degrees.
We conjecture that E[FG] <=O(n) for any simple n-vertex graph G.