TY - GEN

T1 - Approximation algorithms for Euler genus and related problems

AU - Chekuri, Chandra

AU - Sidiropoulos, Anastasios

PY - 2013/12/1

Y1 - 2013/12/1

N2 - The Euler genus of a graph is a fundamental and well-studied parameter in graph theory and topology. Computing it has been shown to be NP-hard by Thomassen [23], [24], and it is known to be fixed-parameter tractable. However, the approximability of the Euler genus is wide open. While the existence of an O(1)-approximation is not ruled out, only an O( √ n)-approximation [3] is known even in bounded degree graphs. In this paper we give a polynomialtime algorithm which on input a bounded-degree graph of Euler genus g, computes a drawing into a surface of Euler genus gO(1).logO(1) n. Combined with the upper bound from [3], our result also implies a O(n1/2-α)- approximation, for some constant α > 0. Using our algorithm for approximating the Euler genus as a subroutine, we obtain, in a unified fashion, algorithms with approximation ratios of the form OPTO(1).logO(1) n for several related problems on bounded degree graphs. These include the problems of orientable genus, crossing number, and planar edge and vertex deletion problems. Our algorithm and proof of correctness for the crossing number problem is simpler compared to the long and difficult proof in the recent breakthrough by Chuzhoy [5], while essentially obtaining a qualitatively similar result. For planar edge and vertex deletion problems our results are the first to obtain a bound of form poly(OPT, log n). We also highlight some further applications of our results in the design of algorithms for graphs with small genus. Many such algorithms require that a drawing of the graph is given as part of the input. Our results imply that in several interesting cases, we can implement such algorithms even when the drawing is unknown.

AB - The Euler genus of a graph is a fundamental and well-studied parameter in graph theory and topology. Computing it has been shown to be NP-hard by Thomassen [23], [24], and it is known to be fixed-parameter tractable. However, the approximability of the Euler genus is wide open. While the existence of an O(1)-approximation is not ruled out, only an O( √ n)-approximation [3] is known even in bounded degree graphs. In this paper we give a polynomialtime algorithm which on input a bounded-degree graph of Euler genus g, computes a drawing into a surface of Euler genus gO(1).logO(1) n. Combined with the upper bound from [3], our result also implies a O(n1/2-α)- approximation, for some constant α > 0. Using our algorithm for approximating the Euler genus as a subroutine, we obtain, in a unified fashion, algorithms with approximation ratios of the form OPTO(1).logO(1) n for several related problems on bounded degree graphs. These include the problems of orientable genus, crossing number, and planar edge and vertex deletion problems. Our algorithm and proof of correctness for the crossing number problem is simpler compared to the long and difficult proof in the recent breakthrough by Chuzhoy [5], while essentially obtaining a qualitatively similar result. For planar edge and vertex deletion problems our results are the first to obtain a bound of form poly(OPT, log n). We also highlight some further applications of our results in the design of algorithms for graphs with small genus. Many such algorithms require that a drawing of the graph is given as part of the input. Our results imply that in several interesting cases, we can implement such algorithms even when the drawing is unknown.

UR - http://www.scopus.com/inward/record.url?scp=84893443249&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893443249&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2013.26

DO - 10.1109/FOCS.2013.26

M3 - Conference contribution

AN - SCOPUS:84893443249

SN - 9780769551357

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 167

EP - 176

BT - Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013

T2 - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013

Y2 - 27 October 2013 through 29 October 2013

ER -