Simple greedy 2-approximation algorithm for the maximum genus of a graph

DOI10.4230/OASICS.SOSA.2019.14MaRDI QIDQ6593569zbMATH OpenFDO

Authors Michal Kotrbčík, Martin Škoviera

Publication date 26 August 2024

Full work available at URL https://doi.org/10.4230/OASICS.SOSA.2019.14

zbMATH Keywords

embeddinggreedy algorithmgraph algorithmmaximum genus

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Locally-maximal embeddings of graphs in orientable surfaces
• scientific article; zbMATH DE number 5657419
• Fundamental cycles and graph embeddings
• scientific article; zbMATH DE number 3900781
• A relative maximum genus graph embedding and its local maximum genus

This page was built for publication: Simple greedy 2-approximation algorithm for the maximum genus of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6593569)