I am learning following famous theorem about planar graph in Bondy’s textbook published in 2008 .
Theorem(due to Whitney(1983)) Every simple 3-connected planar graph has unique planar embedding.
A planar graph for which any two planar embeddings are equivalent is said have an unique embedding in the plane.
The book about embedding equivalence is described as follows:
We say that two planar embeddings of a planar graph G are equivalent if their face boundaries (regarded as sets of edges) are identical.
I can’t understand the meaning of embedding equivalent. Especially, what is called "face boundaries (regarded as sets of edges) are identical"?
Another definition of drawing equivalence I saw in the link below is easy to understand.
is-there-a-planar-graph-with-two-inequivalent-embeddings-on-the-sphere
Two embeddings of a graph on the plane are equivalent if there is a homotopy of topological spaces from one to the other during which the graph does not intersect itself.
This definition is also mentioned in the monograph on crossing numbers.
We only need to limit the definition to plane drawing.
- Schaefer M. Crossing numbers of graphs[M]. CRC Press, 2018.
Based on this definition, we can easily judge that the following two plane drawings of graph are not equivalent.
The following two are also not equivalent.
I would like to ask how to use the definition of Bondy textbook to determine whether they are equivalent.
A more confusing thing is whether the definitions about equivalent embedding (or isomorphic embedding) in the above two books are equivalent? Why?
To apply the definition in Bondy's textbook, we first have to give the vertices names so we can refer to them:
In the first graph, the external face has boundary $\{ab, ad, bc, cd\}$ and the internal face has boundary $\{ab, ad, bc, be, cd, df\}$, when regarded as edge sets. In the second graph, the external face has boundary $\{ab, ad, bc, be, cd\}$ and the internal face has boundary $\{ab, ad, bc, cd, df\}$. The drawings are not equivalent.
Note that we do not care which order the faces are written in, and which face is external. In a third drawing with both leaves on the outside, the external face would have boundary $\{ab, ad, bc, be, cd, df\}$ and the internal face would have boundary $\{ab, ad, bc, cd\}$. This would be equivalent to the first drawing.
The definition in Bondy's textbook (the edge-set definition) is not equivalent to the homotopy definition. The second example you gave illustrates that. In the edge-set definition, the two embeddings are equivalent: there is only one face, and its boundary is the set of all edges in the graph. (In fact, in the edge-set definition, every tree has a unique embedding.)
There is another combinatorial approach to embedding equivalence. You could call this the face-walk definition. For every face, you write down the closed walk that goes around its boundary in order. For example, for the first graph above, the external face has closed walk $(a,b,c,d,a)$ and the internal face has closed walk $(a,b,e,b,c,d,f,d,a)$. We say that two closed walks are equivalent if we can turn one into the other by possibly choosing a different starting point and/or reversing it, and two embeddings are equivalent if their faces have equivalent closed walks.
This definition distinguishes different embeddings of a tree, and is essentially the same as the homotopy definition. You have to be a bit careful, because as I've stated it, it's not always defined when the graph is not connected, but we can resolve that by allowing a face to have multiple closed walk boundaries.