<p>[Reposting comment as an answer, based on the OP's response to the comment.]</p>

<p>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$. </p>

<p>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. (Isotopy is, for example, the topological relation typically used to define two knots as being equivalent.)</p>

CC BY-SA 3.0
2012-11-03T16:45:24.823Z
2012-11-03T16:45:24.823Z
Joshua Grochow
<p>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. </p>

<p>The only definition I found was: </p>

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

<p>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.</p>

CC BY-SA 3.0
2012-11-01T20:34:50.077Z
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?
Kaveh
CC BY-SA 3.0
2012-11-01T23:54:42.273Z
@Kaveh Yes, I guess the definition involving the circular ordering around the vertices would give me this, but only for connected graphs.
IV1
CC BY-SA 3.0
2012-11-02T00:05:37.293Z
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?
Joshua Grochow
CC BY-SA 3.0
2012-11-02T18:28:39.927Z
@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
CC BY-SA 3.0
2012-11-03T16:42:44.770Z
@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).
Joshua Grochow
CC BY-SA 4.0
2018-10-31T11:27:02.550Z
Could you give the reference where you took this definition?
Jonathan Prieto-Cubides
<reference-request><graph-theory><co.combinatorics><terminology><topological-graph-theory>
Equivalent embeddings of a graph
IV1
# Equivalent embeddings of a graph

(Asked by: username_0 on 2012-11-01)

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.

**Tags:** reference-request, graph-theory, co.combinatorics, terminology, topological-graph-theory
> **Comments:**
> **username_1**: 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?  
> **username_0**: @Kaveh Yes, I guess the definition involving the circular ordering around the vertices would give me this, but only for connected graphs.  
> **username_2**: 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?  
> **username_0**: @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.  
> **username_2**: @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).  
> **username_3**: Could you give the reference where you took this definition?  

---

## 1 answers

### Answer by username_2 on 2012-11-03. Score: 1 | Accepted answer

[Reposting comment as an answer, based on the OP's response to the comment.]

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$.

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. (Isotopy is, for example, the topological relation typically used to define two knots as being equivalent.)


---

