On the Genus of Random Regular Graphs

Topological graph theory is a branch of mathematics that studies the topological properties of graphs and their embeddings on surfaces. It combines techniques from topology, algebraic geometry, and combinatorics to study the structure and properties of graphs. This field of mathematics is particularly useful for understanding the global properties of graphs, such as connectivity, and for studying the way in which graphs can be embedded in the plane or in more complicated topological spaces.

One central concept in topological graph theory is that of graph genus. The classification theorem for compact surfaces, first proposed by Möbius in the early 1860s [12] (though not proved rigorously until the 1920s by Brahana [8]), states that all closed surfaces are homeomorphic to spheres with some number of handles or crosscaps attached. We denote a sphere with $g$ handles attached $S_{g}$. This $g$ is called the genus of the surface. The orientable genus of a graph $G$, $\gamma(G)$, is a topological invariant denoting the smallest number $g$ such that $G$ can be drawn onto the orientable surface $S_{g}$ without any edge crossings. In the simplest case, a graph with genus $0$ — i.e., a planar graph — can be drawn on the plane without edge crossings. A graph of genus 1 can be drawn without edge crossings on a torus, a graph of genus 2 on a surface with two handles, and so forth.

Much of the literature in topological graph theory focuses on the study of the embeddings of certain families of graphs, such as complete graphs [13], wheel graphs [10], and complete bipartite (and more generally, $k$-partite) graphs [7, 5], to name a few. Many graph problems, such as the problem of finding a maximal independent set, finding a minimum $t$-spanner, the sparsest-cut problem, and several constraint satisfaction problems, are NP-hard for graphs of genus greater than zero [4, 1, 11, 9]. Therefore, the genus of a graph can be an important measure of complexity in analyzing the efficiency of graph algorithms. Determining the genus of an arbitrary graph is hard, however. In fact, we know the graph genus problem to be NP-complete [14].

The goal of this paper is to characterize the growth of the typical genus of a random regular graph, which can range from 0 in the case of planar graphs to the genus of the complete graph $K_{n}$, $\left\lceil\frac{(n-3)(n-4)}{12}\right\rceil$, as per [13]. Related work has been performed by Asplund et al. [3], who investigate the so-called $k$-planar crossing number of random regular graphs, another metric of how “distant” a graph is from being planar; however, the $k$-planar crossing number of a graph and its genus can be arbitrarily far apart. Additionally, Archdeacon and Grable have showed that the genus of the Erdős-Rényi graph grows as $\frac{n^{2}}{24}$ [2]. However, as we show here, the genus of a random $d$-regular graph grows with high probability as $\frac{d-2}{4}n$ where $n$ is the number of nodes.

We begin by bounding the number of cycles on the graph, which provides a bound on the number of faces, which in turn can then be used in conjunction with Euler’s formula to describe the asymptotic growth of the genus. We say that an event occurs with high probability (w.h.p.) if it’s probability goes to 1 as $n\to\infty$. For a function $f(G)$ of a random $d$-regular graph and a function $h(n)$, we say that $f(G)=o(h(n))$ w.h.p. if $f(G)<ch(n)$ w.h.p. for any $c>0$. We will use $h(n)=n$ and $h(n)=1$.

Proof. We will first show that the expected number of such cycles is $O(1)$.

Markov’s inequality states that if $X$ is a non-negative random variable, then for all $t$,

${Pr}\left[X\geq t\right]\leq\mathbb{E}\left[X\right]/t$.

There are $\frac{t!}{2t}$ possible ways to connect $t$ vertices in a cycle. For sufficiently large $n$, due to the fact that $m$ is a constant, even if we condition upon there being $m$ edges, there are still almost $dn$ “half edges” available, meaning the probability that a given set of t vertices forms a cycle in a particular order is less than $(d/n)^{t}$.

We sum over all possible orderings, and arrive on a bound for the number of cycles of length $\leq m$ of

Proof. For a given random-regular graph, let $\alpha$ denote $g/n$, where $g$ is the graph’s genus and $n$ is the number of nodes.

Euler’s formula states that:

$V-E+F=2-2g$

To show our result, we will show that $F/E$ is $o(1)$ w.h.p. Let $c(m)$ denote the number of faces of length $m$ or less. Since each of these faces includes at least one edge, the other $F-c(m)$ faces have at least $m$ edges each, and each edge can appear in at most two faces, we have:

$F/E\leq 2/m+(1-1/m)c(m)/E$.

$F/E\leq 2/m+(1-1/m)c(m)/E\leq 2/m+o(1)$.

This holds for any constant $m$ meaning $F/E=o(1)$ w.h.p. Consequently, in combination with ($\star$ ‣ 2), we have

$\alpha\geq\frac{d-2}{4}-o(1)$

Numerical experiments show that for small $n$, the genus grows much slower than $\frac{(d-2)n}{4}$. Figure 1 shows that for random 3-regular graphs, $\alpha$ is around $\frac{1}{15}$, significantly less than the expected asymptotic $\frac{1}{4}$.

The data in figure 1 was calculated by a rotational embedding scheme that was implemented in the functional programming language Haskell. The details of this algorithm are described in [6]. A rotation system describes a cyclic ordering of neighbors of each vertex that describes an embedding of the graph. The algorithm for determining genus via a rotational embedding scheme involves brute-forcing every possible cyclic embedding around each node, resulting in different permutations of orderings around each vertex that are homeomorphic to the sphere, also called 2-cells (meaning that they themselves are planar), which can then be used to find minimum genus [6]. Due to the NP-hard nature of this algorithm, it can only be practically run on small graphs. In this case graphs up to $n=30$ could be generated, as seen below.

I am highly grateful to Cristopher Moore of the Santa Fe Institute for his mentorship.