# A criterion for the planar graph to have unique dual

I get stuck with the following two criteria both about the uniqueness of plane embeddings of a given planar graph. The first one says that a planar graph admits unique plane embedding iff it is a subdivision of 3-connected planar graph (e.g. from the book "Planar Graphs: Theory and Algorithms"). The second one (is from paper "The uniquely embeddable planar graphs") tells that uniqueness holds iff it is 3-connected planar plus some exclusions. I suppose they are based on two different definitions of equivalence. As for me I consider plane embeddings equivalence as an equivalence of the respective complexes. Indeed, each plane graph is in fact a triple $(V,E,F)$ where $F$ denotes set of faces. So the equivalence means that there is a map that translates the first complex to another one that keeps incidence between vetices and edges, edges and faces, vertices and faces.

My question is particularly under what definition the first criterion holds ? The proof that the book gives is a bit untransparent for me in that matter because the definition of uniqueness that it gives is not that strict.

• The criteria could be equivalent: the first one states that it needs to be a subdivision of a 3-connected planar graph, and the other one states that it must be a bona fide 3-connected planar graph (minus some exceptional cases). Mar 16, 2016 at 12:19
• Regarding the definitions, you can look them up in the book and in the paper. You don't need us for that. Mar 16, 2016 at 12:20
• Those exclusions are planar graphs that have the number of vertices bounded by a constant.
– KKS
Mar 16, 2016 at 12:29
• Both results you state give an if-and-only-if characterization. So the answer to your question, under what definition the first criterion holds, is very simple: it's exactly the definition used where the criterion was proved, a definition which you can look up in the book. If the two criteria are incompatible, then the characterization doesn't hold under the definition in the paper, since both characterizations are if-and-only-ifs. Mar 16, 2016 at 12:34
• The proof from the book seems to be wrong in the case when one of graphs $G_i$ is symmetric under twists and reflections. Searching I found that book criteria is of limited use.
– KKS
Mar 16, 2016 at 13:23

First let me mention that the definition of being uniquely embeddable requires ANY graph isomorphism (e.g. just renaming symmetric vertices or any other automorphism permutation) to be (not necessary uniquely) extendable to topological (or combinatorial) one (see Diestel Graph Theory chapter about planar graphs for these definitions) in contrast to usual understanding of this definition that for any two planar embeddings there EXISTS some topological (or combinatorial) isomorphism. Difference between the topological and combinatorial isomorphism definitions is negligible for 2-connected planar graphs (see Diestel book). This particularly means that if we reflect or twist some symmetric graph (as done in the proof of necessity of the aforementioned criterion "subdivision of 3-connected planar graph if and only if condition to be embeddable" in the book "Planar Graphs: Theory and Algorithms") we get topologically non-isomorphic graph in general. Though $K_{2,3}$ graph witnesses that the necessity proof here is wrong but the sufficiency is hold.