Conditions on graphs to assure unique embedding on a fixed genus surface

Question

The classical Whitney Theorem in low topological theory/graph theory states that every 3-connected planar graph is uniquely embeddable (up to orientation) on the sphere.

My question is the following: let's consider an small genus surface (for instance, the projective plane or the torus with only 1 hole). This result is already not true, but I was wondering which extra conditions one may ask of the graph we want to embed to assure uniqueness on the embedding.

Of course here we are asking about "cellular embeddings" (all faces defined by the embedding are contractible)

I know a result due to Robertson and Vitray concerning representability of the graph, but I would like to know if there are more results in this direction (concerning, for instance, vertex degrees, minimum level of connectivity, etc.)

Answer 1

One condition is that the embedding has "large edge-width," i.e., every noncontractible cycle is longer than every facial walk. Intuitively, I believe that large edge-width can be thought of as having big "planar patches."

In Thomassen, "Embeddings of Graphs with No Short Noncontractible Cycles", the author proves that large edge-width plus 3-connectivity yields a Whitney's theorem analogue. There are other analogies with planar graphs, including a 5-coloring result, and these are spelled out in the book "Graphs on Surfaces" by Mohar and Thomassen.