# Equivalent embeddings of a graph

I have difficulties finding a good definition of two embeddings of a (planar) graph in the plane being equivalent. Intuitively I mean by equivalent that the embeddings look the same up to homeomorphism of the faces.

The only definition I found was:

Two embeddings of a graph are equivalent if for each vertex all
incident edges have the same circular clockwise order in both embeddings.


But this is not strong enough to match my intuitive view, since this notion of equivalence allows connected components to be arbitrarily contained in each other.

• You consider two embedding to be equivalent only when you can transform one to the other one by continuously moving vertices and edges with no move causing a crossing, do I understand correctly? Nov 1, 2012 at 20:34
• @Kaveh Yes, I guess the definition involving the circular ordering around the vertices would give me this, but only for connected graphs.
– IV1
Nov 1, 2012 at 23:54
• Then it seems like what you're looking for is a circular ordering around the vertices together with a map $f$ from the set of components to the set of faces such that $f(C_i)$ is the face of the graph that contains the component $C_i$... If you prefer a topological definition, I believe what you're looking for is that the map between the graphs can be extended to a map from the plane to itself that is isotopic to the identity. I'm not quite sure why you're asking this on this particular site (as opposed to, say, mathoverflow or math.SE) - did you have some CS motivation in mind? Nov 2, 2012 at 0:05
• @Joshua Grochow Thank you for your comment. Your idea works fine. I am amazed though that I can not find any reference to any such definition of equivalence of embeddings. And sorry for posting it on the "wrong" site, the problems appears in some hardness reduction.
– IV1
Nov 2, 2012 at 18:28
• @IV1: It's not that this is the "wrong" site, but just that it would've been nice to know what CS-related motivation you had for the question (e.g. a reference to the hardness reduction in which it appears). Nov 3, 2012 at 16:42

For a combinatorial definition, it seems like what you're looking for is a circular ordering around the vertices together with a map $f$ from the set of components to the set of faces such that $f(C_i)$ is the face of the graph that contains the component $C_i$.