A note on approximating graph genus

DOI10.1016/S0020-0190(97)00203-2MaRDI QIDQ290221zbMATH OpenFDO

Authors Saroja P. Kanchi, Arkady Kanevsky, Jianer Chen

Publication date 1 June 2016

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

zbMATH Keywords

approximation algorithmgraph embeddingcombinatorial problemscombinatorial analysis

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 3970774 (Why is no real title available?)
• scientific article; zbMATH DE number 4006288 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• Algorithmic graph embeddings
• Efficient Planarity Testing
• Hierarchy for imbedding-distribution invariants of a graph
• On the complexity of graph embeddings
• On the hardness of approximating minimization problems
• The graph genus problem is NP-complete

Cited in

(11)

• Embeddings of graphs of fixed treewidth and bounded degree
• Genus characterizes the complexity of certain graph problems: Some tight results
• Beyond the Euler characteristic: approximating the genus of general graphs (extended abstract)
• The thickness of amalgamations and Cartesian product of graphs
• Polylogarithmic approximation for Euler genus on bounded degree graphs
• Approximation algorithms for Euler genus and related problems
• scientific article; zbMATH DE number 7266394 (Why is no real title available?)
• On the complexity of graph embeddings
• Deleting vertices to graphs of bounded genus
• A pseudo-approximation for the genus of Hamiltonian graphs
• A pseudo-approximation for the genus of Hamiltonian graphs

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)