Approximation algorithms for Euler genus and related problems
From MaRDI portal
Publication:4581910
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.
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
Cites work
- scientific article; zbMATH DE number 5485473 (Why is no real title available?)
- scientific article; zbMATH DE number 2230213 (Why is no real title available?)
- 103 graphs that are irreducible for the projective plane
- A Better Approximation Algorithm for Finding Planar Subgraphs
- A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
- A framework for solving VLSI graph layout problems
- A kuratowski theorem for the projective plane
- A near-optimal approximation algorithm for asymmetric TSP on embedded graphs
- A note on approximating graph genus
- A pseudo-approximation for the genus of Hamiltonian graphs
- Adding one edge to planar graphs makes crossing number and 1-planarity hard
- An algorithm for the graph crossing number problem
- Call routing and the ratcatcher
- Combinatorial Local Planarity and the Width of Graph Embeddings
- Computing crossing numbers in quadratic time
- Computing the orientable genus of projective graphs
- Computing the shortest essential cycle
- Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
- Edge-disjoint paths in planar graphs with constant congestion
- Efficient Planarity Testing
- Embeddings of graphs with no short noncontractible cycles
- Face covers and the genus problem for apex graphs
- Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
- Finding shortest non-trivial cycles in directed graphs on surfaces
- Graph minors. V. Excluding a planar graph
- 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
- Graphs on surfaces
- Grid minors in damaged grids
- Hardness of approximation for crossing number
- Holiest minimum-cost paths and flows in surface graphs
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Minimal embeddings in the projective plane
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- On graph crossing number and edge planarization
- On the complexity of the approximation of nonplanarity parameters for cubic graphs
- Optimally cutting a surface into a disk
- Quickly excluding a planar graph
- Separating and nonseparating disjoint homotopic cycles in graph embeddings
- Shortest non-trivial cycles in directed and undirected surface graphs
- Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
- The asymmetric traveling salesman problem on graphs with bounded genus
- The graph genus problem is NP-complete
- Topological graph theory.
- Triangulating a surface with a prescribed graph
Cited in
(12)- Beyond the Euler characteristic: approximating the genus of general graphs (extended abstract)
- A practical algorithm for the computation of the genus
- Polylogarithmic approximation for Euler genus on bounded degree graphs
- Grid minors in damaged grids
- Planar drawings of higher-genus graphs
- Deleting vertices to graphs of bounded genus
- Stronger ILPs for the Graph Genus Problem.
- The degenerate crossing number and higher-genus embeddings
- A pseudo-approximation for the genus of Hamiltonian graphs
- A pseudo-approximation for the genus of Hamiltonian graphs
- Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
- A note on approximating graph genus
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)
