Graph $G$ can be embedded (or has an embedding) in the space if $G$ can be drawn in the space if $G$ can be drawn in such a way that no two edges cross except at an end-vertex in common. A Graph $G$ is planar if $G$ has an embedding in the plane. Two embeddings of a planar graph are equivalent when the boundary of a face in one embedding always corresponds to the boundary of a face in the other. We say that the plane embedding of a graph is unique when all the embeddings are equivalent.
Whitney proved that the embedding of a 3-connected planar graph is unique. However, when the connectivity of a planar graph is 1 or 2, this uniqueness cannot be guaranteed. For example, the left and right embeddings of the following graph are not equivalent.
Another example,
So is there any research on counting the number of non-equivalent embeddings for given planar graphs or listing these embeddings?
Are there relevant program implementations in practical applications? I know that there are two nice programs, nauty
and plantri
, I have not been able to find what I'm looking for.
Interestingly, in the monograph Planar graph drawing ( T. Nishizeki), I see the following theorem.
Theorem 2.2.2 The embedding of a 2-connected planar graph $G$ is unique if and only if $G$ is a subdivision of a 3-connected graph.
However, even determining the uniqueness of embeddings through the analysis of whether $G$ is a subdivision of a 3-connected graph is not an easy task.