Approximation Algorithms for Euler Genus and Related Problems
From MaRDI portal
Publication:4581910
DOI10.1137/14099228XzbMath1398.68663arXiv1304.2416OpenAlexW2886408974WikidataQ129376047 ScholiaQ129376047MaRDI QIDQ4581910
Chandra Chekuri, Anastasios Sidiropoulos
Publication date: 21 August 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1304.2416
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (3)
Grid minors in damaged grids ⋮ Stronger ILPs for the Graph Genus Problem. ⋮ The Degenerate Crossing Number and Higher-Genus Embeddings
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on approximating graph genus
- Grid minors in damaged grids
- Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
- Computing the shortest essential cycle
- A framework for solving VLSI graph layout problems
- Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
- Embeddings of graphs with no short noncontractible cycles
- Graph minors. V. Excluding a planar graph
- 103 graphs that are irreducible for the projective plane
- Triangulating a surface with a prescribed graph
- Call routing and the ratcatcher
- Quickly excluding a planar graph
- Graph minors. XVI: Excluding a non-planar graph
- Optimally cutting a surface into a disk
- On the complexity of the approximation of nonplanarity parameters for cubic graphs
- Face covers and the genus problem for apex graphs
- Computing crossing numbers in quadratic time
- Separating and nonseparating disjoint homotopic cycles in graph embeddings
- Hardness of approximation for crossing number
- A tighter insertion-based approximation of the crossing number
- Graph minors. VIII: A Kuratowski theorem for general surfaces
- A Pseudo-approximation for the Genus of Hamiltonian Graphs
- Edge-disjoint paths in Planar graphs with constant congestion
- Finding shortest non-trivial cycles in directed graphs on surfaces
- The graph genus problem is NP-complete
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- A kuratowski theorem for the projective plane
- Combinatorial Local Planarity and the Width of Graph Embeddings
- Efficient Planarity Testing
- A Better Approximation Algorithm for Finding Planar Subgraphs
- A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
- Minimal embeddings in the projective plane
- A near-optimal approximation algorithm for Asymmetric TSP on embedded graphs
- Computing the orientable genus of projective graphs
- Holiest minimum-cost paths and flows in surface graphs
- Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
- An algorithm for the graph crossing number problem
- Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs
This page was built for publication: Approximation Algorithms for Euler Genus and Related Problems
