The complexity of embedding a graph into a variety of topological surfaces is investigated. A new data structure for graph embeddings is introduced and shown to be superior to the previously known data structures. In particular, the new data structure efficiently supports all on-line operations for general graph embeddings. Based on this new data structure, very efficient algorithms are developed to solve the problem “given a graph G and an integer k, construct a genus k embedding for the graph G” for a large range of the integers k and for a large class of graphs.