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

Michal Kotrbcik, Martin Skoviera

The maximum genus ${\gamma }_M(G)$ of a graph G is the largest genus of an orientable surface into which G has a cellular embedding. Combinatorially, it coincides with the maximum number o…