On determining the genus of a graph in O(v ^O(g)) steps(Preliminary Report)

Abstract

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.