World's most popular travel blog for travel bloggers.

[Solved]: A criterion for the planar graph to have unique dual

, , No Comments
Problem Detail: 

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.

Asked By : KKS

Answered By : KKS

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54540

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback