Efficient polynomial-time approximation scheme for the genus of dense graphs

Abstract

The main results of this paper provide an Efficient Polynomial-Time Approximation Scheme (EPTAS) for approximating the genus (and non-orientable genus) of dense graphs. By dense we mean that $|E(G)|\ge \alpha |V(G){|}^2$ for some fixed $\alpha >0$. While a constant factor approximation is trivial for this class of graphs, approximations with factor arbitrarily close to 1 need a sophisticated algorithm and complicated mathematical justification. More precisely, we provide an algorithm that for a given (dense) graph $G$ of order $n$ and given $\epsilon >0$, returns an integer $g$ such that $G$ has an embedding into a surface of genus $g$, and this is $\epsilon$-close to a minimum genus embedding in the sense that the minimum genus $\mathsf{g}(G)$ of $G$ satisfies: $\mathsf{g}(G)\le g\le (1+\epsilon )\mathsf{g}(G)$. The running time of the algorithm is $O(f(\epsilon )n^2)$, where $f(\cdot )$ is an explicit function. Next, we extend this algorithm to also output an embedding (rotation system) whose genus is $g$. This second algorithm is an Efficient Polynomial-time Randomized Approximation Scheme (EPRAS) and runs in time $O(f_1(\epsilon )n^2)$.

36 pages. An extended abstract of the preliminary version of this paper appeared in FOCS 2018; to appear in JACM

References in corpus (2)

• On regularity lemmas and their algorithmic applications
• Computational topology of graphs on surfaces