A note on approximating graph genus

DOI10.1016/S0020-0190(97)00203-2zbMath1337.68126MaRDI QIDQ290221

Arkady Kanevsky, Saroja P. Kanchi, Jian'er Chen

Publication date: 1 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmcombinatorial problemscombinatorial analysisgraph embedding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

The thickness of amalgamations and Cartesian product of graphs ⋮ Genus characterizes the complexity of certain graph problems: Some tight results ⋮ Approximation Algorithms for Euler Genus and Related Problems

Cites Work

• Algorithmic graph embeddings
• The graph genus problem is NP-complete
• Hierarchy for imbedding-distribution invariants of a graph
• Efficient Planarity Testing
• On the hardness of approximating minimization problems
• On the complexity of graph embeddings
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item