See the article Embedding graphs in surfaces: MacLanes theorem for higher genus  authored by H. Bruhn and R. Diestel, (file attached)

See the article Embedding graphs in surfaces: MacLanes theorem for higher genus  authored by H. Bruhn and R. Diestel, (file attached)

I know of one paper of Bojan Mohar called "Embedding graphs in an arbitrary surface in linear time" (see link). Maybe you have to do little bit of further research to find one version for download.

http://dl.acm.org/citation.cfm?id=237986

Thanks, Naduvath and Korimort. However, both papers seems slightly different from my question. In my question, the embedding is given, we need to check if it is a minimum genus embedding. (Of course, we are not assumed to be aware of the (minimum) genus of the graph.) 

On determining the genus of a graph. (see link). Maybe this can help you also.

http://citeseerx.ist.psu.edu/showciting;jsessionid=5456B19259B8AC5CC4146433A1FEC1B2?cid=375889

I found that "embeddings of graphs with no short non contractible cycles" by Thomassen is more related to my question. But, he gave sufficient conditions in the paper instead of necessary conditions.

You see a book by Bojan Mohar and Carsten Thomassen "Graphs on Surfaces".

Thanks Tingzeng and all. From the material I have found so far, it seems there aren't (many) necessary conditions for an embedding of a graph to be a minimum genus embedding of the graph.

We obtained an easy-to-check necessary condition for an embedding of the graph G to be an embedding with the minimum genus of G recently.

For those might be interested: The said necessary condition in my last comment can be found in the paper "On the local genus distribution of graph embeddings, Journal of Combinatorial Mathematics and Combinatorial Computing, 101 (2017), pp. 157-173".