  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 of disjoint pairs of adjacent edges of G
whose removal results in a connected spanning subgraph of G. In this paper we
prove that removing pairs of adjacent edges from G arbitrarily while retaining
connectedness leads to at least $\gamma_M(G)/2$ pairs of edges removed. This
allows us to describe a greedy algorithm for the maximum genus of a graph; our
algorithm returns an integer k such that $\gamma_M(G)/2\le k \le \gamma_M(G)$,
providing a simple method to efficiently approximate maximum genus. As a
consequence of our approach we obtain a 2-approximate counterpart of Xuong's
combinatorial characterisation of maximum genus.
