2020/11/16 by Yifan Jing, Jing, Yifan, Bojan Mohar +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2011.08049
openalex created_date 2018/08/31 · openalex publication_date 2020/11/16 · openalex updated_date 2026/07/28
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)|≥ α|V(G)|2 for some fixed α>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 ε>0, returns an integer g such that G has an embedding into a surface of genus g, and this is ε-close to a minimum genus embedding in the sense that the minimum genus g(G) of G satisfies: g(G)≤ g≤ (1+ε)g(G). The running time of the algorithm is O(f(ε) n2), where f(⋅) 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(f1(ε) n2).