The problem of finding the graph genus is NP-hard (the problem of determining whether an n-vertex graph has genus g is NP-complete) [REF].
The first breakthrough in this respect happened in 1979, when algorithms of time complexity O(nO(g)) were independently submitted to the Annual ACM Symposium on Theory of Computing: one by I. Filotti and G.L. Miller and another one by John Reif.