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.

  • $\begingroup$ 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). $\endgroup$ – Yuval Filmus Mar 16 '16 at 12:19
  • $\begingroup$ Regarding the definitions, you can look them up in the book and in the paper. You don't need us for that. $\endgroup$ – Yuval Filmus Mar 16 '16 at 12:20
  • $\begingroup$ Those exclusions are planar graphs that have the number of vertices bounded by a constant. $\endgroup$ – KKS Mar 16 '16 at 12:29
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 16 '16 at 12:34
  • $\begingroup$ 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. $\endgroup$ – KKS Mar 16 '16 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.

What I mean by complex-based isomorphism is just combinatorial one from Diestel book.

If we allow my unusual definition of uniqueness that any two embeddings are topologically isomorphic then there is an example of 2-connected non-subdivisions that are uniquely embeddable.

As for aforementioned paper "Uniquely embeddable planar graphs" the special definition which is given there is tougher (not robust to transposition of symmetric vertices) (but close to as Yuval assumed) than topological isomorphism according to its Theorem 3.5.

  • 1
    $\begingroup$ Perhaps you can add more details in your answer, to make it more useful in the future. $\endgroup$ – Yuval Filmus Mar 16 '16 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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