On determining the genus of a graph in O(v O(g)) steps(Preliminary Report)
I. S. Filotti, Gary Lee Miller, John H. Reif · 1979
In this paper we present an algorithm which on input a graph G and a positive integer g finds an embedding of G on a surface on genius g, if such an embedding exists. This algorithm runs in (v) O(g) steps where v is the number of vertices of G.