6
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Kaveh
    Nov 1, 2012 at 20:34
  • $\begingroup$ @Kaveh Yes, I guess the definition involving the circular ordering around the vertices would give me this, but only for connected graphs. $\endgroup$
    – IV1
    Nov 1, 2012 at 23:54
  • 2
    $\begingroup$ 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? $\endgroup$
    – Joshua Grochow
    Nov 2, 2012 at 0:05
  • 1
    $\begingroup$ @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. $\endgroup$
    – IV1
    Nov 2, 2012 at 18:28
  • $\begingroup$ @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). $\endgroup$
    – Joshua Grochow
    Nov 3, 2012 at 16:42

1 Answer 1

Reset to default
1
$\begingroup$

[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.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.