The genus of generalized random and quasirandom graphs

The genus of a graph $G$ is the minimum integer $h$ such that $G$ has an embedding in some surface (closed compact 2-manifold) $S_h$ of genus $h$. In this thesis, we will discuss the genus of generalized random and quasirandom graphs. First, by developing a general notion of random graphs, we determine the genus of generalized random graphs. Next, we approximate the genus of dense generalized quasirandom graphs. Based on analysis of minimum genus embeddings of quasirandom graphs, we provide an Efficient Polynomial-Time Approximation Scheme (EPTAS) for approximating the genus (and non-orientable genus) of dense graphs. More precisely, we provide an algorithm that for a given (dense) graph $G$ of order $n$ and given $\varepsilon>0$, returns an integer $g$ such that $G$ has an embedding into a surface of genus $g$, and this is $\varepsilon$-close to a minimum genus embedding in the sense that the minimum genus $\g(G)$ of $G$ satisfies: $\g(G)\le g\le (1+\varepsilon)\g(G)$. The running time of the algorithm is $O(f(\varepsilon) n^2)$, where $f(\cdot)$ is an explicit function. Next, we extend this algorithm to also output an embedding (rotation system) of genus $g$. This second algorithm is an Efficient Polynomial-time Randomized Approximation Scheme (EPRAS) and runs in time $O(f_1(\varepsilon)\,n^2)$. The last part of the thesis studies the genus of complete $3$-uniform hypergraphs, which is a special case of genus of random bipartite graphs, and also a natural generalization of Ringel--Youngs Theorem. Embeddings of a hypergraph $H$ are defined as the embeddings of its associated Levi graph $L_H$ with vertex set $V(H)\cup E(H)$, in which $v\in V(H)$ and $e\in E(H)$ are adjacent if and only if $v$ and $e$ are incident in $H$. The construction in the proof may be of independent interest as a design-type problem.