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

Jesse Campion Loth, Kevin Halasz, Tomáš Masařík +2

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 fa…