On the Genus of Random Regular Graphs

The genus of a graph is a topological invariant that measures the minimum genus of a surface on which the graph can be embedded without any edges crossing. Graph genus plays a fundamental role in topological graph theory, used to classify and study different types of graphs and their properties. We show that, for any integer $d\ge 2$, the genus of a random $d$-regular graph on $n$ nodes is $\frac{(d-2)}{4}n(1-\epsilon )$ with high probability for any $\epsilon >0$.