A relative maximum genus graph embedding and its local maximum genus

A relative embedding of a connected graph is an embedding of the graph in some surface with respect to some closed walks, each of which bounds a face of the embedding. The relative maximum genus of a connected graph is the maximum of integerk with the property that the graph has a relative embedding in the orientable surface withk handles. A polynomial algorithm is provided for constructing relative maximum genus embedding of a graph if the relative tree of the graph is planar. Under this condition, just like maximum genus embedding, a graph does not have any locally strict maximum genus.