A note on approximating graph genus
From MaRDI portal
Publication:290221
DOI10.1016/S0020-0190(97)00203-2zbMATH Open1337.68126MaRDI QIDQ290221FDOQ290221
Authors: Saroja P. Kanchi, Arkady Kanevsky, Jianer Chen 
Publication date: 1 June 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Recommendations
- On the complexity of graph embeddings
- Beyond the Euler characteristic: approximating the genus of general graphs (extended abstract)
- Approximation algorithms for Euler genus and related problems
- Polylogarithmic approximation for Euler genus on bounded degree graphs
- scientific article; zbMATH DE number 867666
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Efficient Planarity Testing
- Title not available (Why is that?)
- Algorithmic graph embeddings
- The graph genus problem is NP-complete
- Hierarchy for imbedding-distribution invariants of a graph
- Title not available (Why is that?)
- On the hardness of approximating minimization problems
- On the complexity of graph embeddings
Cited In (11)
- 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
- On the complexity of graph embeddings
- The thickness of amalgamations and Cartesian product of graphs
- Approximation algorithms for Euler genus and related problems
- Deleting vertices to graphs of bounded genus
- Embeddings of graphs of fixed treewidth and bounded degree
- Title not available (Why is that?)
- Genus characterizes the complexity of certain graph problems: Some tight results
This page was built for publication: A note on approximating graph genus
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q290221)
