Approximation algorithms for Euler genus and related problems

DOI10.1137/14099228XzbMATH Open1398.68663arXiv1304.2416OpenAlexW2886408974WikidataQ129376047 ScholiaQ129376047MaRDI QIDQ4581910FDOQ4581910

Authors: Chandra Chekuri, Anastasios Sidiropoulos 

Publication date: 21 August 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: 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 '89 & '93], 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(sqrt(n))-approximation [Chen, Kanchi, Kanevsky '97] is known even in bounded degree graphs. In this paper we give a polynomial-time algorithm which on input a bounded-degree graph of Euler genus g, computes a drawing into a surface of Euler genus poly(g, log(n)). Combined with the upper bound from [Chen, Kanchi, Kanevsky '97], our result also implies a O(n^(1/2 - alpha))-approximation, for some constant alpha>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 poly(OPT, log(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 2011], 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.

Full work available at URL: https://arxiv.org/abs/1304.2416

Recommendations

• Polylogarithmic approximation for Euler genus on bounded degree graphs
• Beyond the Euler characteristic: approximating the genus of general graphs (extended abstract)
• Deleting vertices to graphs of bounded genus
• A note on approximating graph genus
• Approximating the crossing number of graphs embeddable in any orientable surface

zbMATH Keywords

approximation algorithmscrossing numberEuler genusminimum planarization

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• Call routing and the ratcatcher
• Face covers and the genus problem for apex graphs
• Graphs on surfaces
• Efficient Planarity Testing
• A Better Approximation Algorithm for Finding Planar Subgraphs
• Embeddings of graphs with no short noncontractible cycles
• Graph minors. V. Excluding a planar graph
• 103 graphs that are irreducible for the projective plane
• Quickly excluding a planar graph
• A kuratowski theorem for the projective plane
• Topological graph theory.
• A note on approximating graph genus
• The graph genus problem is NP-complete
• Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
• Adding one edge to planar graphs makes crossing number and 1-planarity hard
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
• A framework for solving VLSI graph layout problems
• Separating and nonseparating disjoint homotopic cycles in graph embeddings
• Graph minors. VIII: A Kuratowski theorem for general surfaces
• Graph minors. XVI: Excluding a non-planar graph
• Graphs of groups on surfaces. Interactions and models
• Edge-disjoint paths in planar graphs with constant congestion
• Grid minors in damaged grids
• Optimally cutting a surface into a disk
• Title not available (Why is that?)
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• Computing the orientable genus of projective graphs
• Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
• Computing crossing numbers in quadratic time
• An algorithm for the graph crossing number problem
• Shortest non-trivial cycles in directed and undirected surface graphs
• On the complexity of the approximation of nonplanarity parameters for cubic graphs
• Computing the shortest essential cycle
• A tighter insertion-based approximation of the crossing number
• Combinatorial Local Planarity and the Width of Graph Embeddings
• Finding shortest non-trivial cycles in directed graphs on surfaces
• Minimal embeddings in the projective plane
• Hardness of approximation for crossing number
• Triangulating a surface with a prescribed graph
• A pseudo-approximation for the genus of Hamiltonian graphs
• On graph crossing number and edge planarization
• The asymmetric traveling salesman problem on graphs with bounded genus
• A near-optimal approximation algorithm for asymmetric TSP on embedded graphs
• Holiest minimum-cost paths and flows in surface graphs
• Title not available (Why is that?)

Cited In (12)

• Polylogarithmic approximation for Euler genus on bounded degree graphs
• Beyond the Euler characteristic: approximating the genus of general graphs (extended abstract)
• A pseudo-approximation for the genus of Hamiltonian graphs
• A pseudo-approximation for the genus of Hamiltonian graphs
• Grid minors in damaged grids
• A note on approximating graph genus
• Deleting vertices to graphs of bounded genus
• Stronger ILPs for the Graph Genus Problem.
• The degenerate crossing number and higher-genus embeddings
• Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
• A practical algorithm for the computation of the genus
• Planar drawings of higher-genus graphs

This page was built for publication: Approximation algorithms for Euler genus and related problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4581910)