Not signed in (Sign In)

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

  • Sign in using OpenID

Site Tag Cloud

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics complex complex-geometry computable-mathematics computer-science constructive cosmology deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration foundation foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory internal-categories k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nlab noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf simplicial space spin-geometry stable-homotopy-theory stack string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).

nLab > nLab General Discussions: Whitney's theorem on uniqueness of embeddings of 3-connected graphs in the plane

Bottom of Page

1 to 36 of 36

  1.  
    • CommentRowNumber1.
    • CommentAuthorRichard Williamson
    • CommentTimeAug 3rd 2017
    • (edited Aug 3rd 2017)

    This is just a quick question which I hope will catch the attention of Noam in particular (but anyone is welcome to contribute).

    For something I am working on in knot theory, I would like to appeal to a classical theorem of Whitney which says that any 3-connected planar graph has a unique embedding in the plane up to planar isotopy. It is not altogether easy to track down the original reference; indeed Noam asked about it here. I have seen at least two other papers cited (incorrectly) in the literature!

    I agree with Noam that Theorem 11 in the paper he mentions seems the correct reference. However, what Whitney actually proves is that every 3-connected planar graph has a unique dual graph. Now, it seems to me that this is equivalent to having a unique embedding (again, up to planar isotopy). However, I have not seen this explicitly stated anywhere in the literature. Do people agree that this is the case, i.e. that unique dual implies unique embedding? If so, I will add some kind of entry to the nLab just to record this and the correct reference.

  2. Hi Richard,

    Thanks for the question! The implication “unique embedding ⇒\Rightarrow unique dual” is immediate by definition if we take “dual” to mean geometric dual (which is defined in terms of an embedding, although Whitney stated his theorem in terms of the combinatorial dual), but the converse is admittedly less obvious to me. I believe it is true, though, based on the following fact (which I also believe, although I’m not sure I’ve seen it explicitly stated anywhere): any duality between a pair of graphs GG and G *G^* uniquely determines an embedding of GG (and G *G^*). In particular, such a duality fixes a bijection between the edges of GG and the edges of G *G^*, which we can use to define a ternary incidence relation between vertices, edges, and faces (= vertices of G *G^*). In turn, we can use this incidence relation to define a triple of involutions on “flags” (= incident vertex-edge-face triples), which uniquely determines an embedding of GG (as a transitive permutation representation of the cartographic group). There might be some subtleties I am overlooking, though, so it would be good to have a reference for this basic property.

  3. To be a bit more explicit, to define the involutions I am relying on the fact that if you fix any flag (v,e,f) of a vertex-edge-face which are mutually incident, then there is exactly one other v’ such that (v’,e,f) are mutually incident, one other e’ such that (v,e’,f) are mutually incident, and one other f’ such that (v,e,f’) are mutually incident. I believe this property is true, but it must rely on the duality between GG and G *G^*.

    • CommentRowNumber4.
    • CommentAuthorRichard Williamson
    • CommentTimeAug 3rd 2017
    • (edited Aug 3rd 2017)

    Thanks for the reply, Noam! That’s an interesting approach. My thinking was slightly different: I was thinking of appealing to the fact that one can characterise plane graph isotopy as an isomorphism between the underlying abstract graphs which induces a bijection between the set of face boundaries of the embedded graphs. For if the (geometric) duals are isomorphic as abstract graphs, then this isomorphism induces an isomorphism of the original graphs which seems to me, more or less immediately from the definition of the (geometric) dual, to induce a bijection between the set of face boundaries (the edges in the boundary of a face in the original graph are in 1-1 correspondence with the edges incident to the vertex of the dual graph corresponding to this face).

    • CommentRowNumber5.
    • CommentAuthorRichard Williamson
    • CommentTimeAug 3rd 2017
    • (edited Aug 3rd 2017)

    It would be interesting to find when the attribution to Whitney of the uniqueness of embedding form of the result first occurred in the literature. Already in the 1969, in Harary’s book, the citation is incorrect, so it must presumably have been some time before that.

  6. By way of google scholar, here’s a 1966 note On the Order of the Group of a Planar Map by Harary and Tutte that mentions “a classical result of Whitney [3]” that “every triply connected planar graph G can be embedded in the plane as a map M in only one way”, where [3] = Congruent Graphs and the Connectivity of Graphs. Since Tutte was deeply familiar with Whitney’s work (from what I understand) that would seem to settle the question of the correct reference…except that I just had a look in “Graph Theory as I Have Known It”, and see that there he also mentions “Whitney’s famous theorem that a 3-connected planar graph can be drawn on the sphere in essentially one way [116]”, where [116] = 2-isomorphic graphs. Oh no! Two authors and three different citations!

  7. Re #4, I’m not sure I completely follow your argument – how do you mean to recover the cyclic order of the edges around each face boundary, as opposed to just the set of edges incident to each face? (Given an embedding represented using involutions, you can recover the cycles by composing involutions, e.g., starting at a flag (v,e,f)(v,e,f), we reflect across the (v,f)(v,f) incidence to get to (v,e′,f)(v,e',f), reflect across the (e′,f)(e',f) incidence to get to (v′,e′,f)(v',e',f), then reflect across (v′,f)(v',f) get to (v′,e″,f)(v',e'',f), and so on, eventually making our way around the perimeter of ff and back to (v,e,f)(v,e,f).)

    • CommentRowNumber8.
    • CommentAuthorPeter Heinig
    • CommentTimeAug 4th 2017
    • (edited Aug 4th 2017)

    Richard,

    Do people agree that this is the case, i.e. that unique dual implies unique embedding?

    This seems false if the following hypotheses are made (I am not sure whether you permit all of these): (0) embedding=embedding into the 2-sphere S 2S^2, (1) infinite graphs are allowed (the word “finite” was not mentioned so far), and (2) for any homeomorphism η:ℝ→S 2\eta\colon\mathbb{R}\rightarrow S^2, the relative complement S 2∖image(η)S^2\setminus\mathrm{image}(\eta) is simply connected. Consider the graph GG == undirected two-way infinite double-ray. Because of (2), any embedding of GG into S 2S^2 has as its dual the countably infinite bouquet (one vertex, ℵ 0\aleph_0-many loops at it), so the geometric dual is unique, yet GG admits more than one embedding modulo isotopy: compare the obvious embedding (with two limit points on either side) with e.g. the embedding according to an infinite logarithmic spiral. These two embeddings seem not to be equivalent under isotopy, for reasons I cannot yet state precisely.

    If you insist on embeddings in the plane, I still do not have a counterexample to your conjecture.

    (EDIT, to clarify: for the plane, the construction sketched above does not contradict your conjecture in the sense that w.r.t. embedding into the plane, the double-ray should not be regarded to have a unique dual since e.g. the obvious embedding into the plane has the countably infintie dipole for its dual, while the embedding with two llmit points on either end has the countably infinite bouquet for its dual, so then your hypothesis is not satisfied.)

    Would you please clarify your conventions? Embeding into the plane or the 2-sphere? Infinite graphs permitted? Which variant of dual? Which equivalence relation on the embeddings?

  9. Thanks very much for your thoughts, Noam! Regarding #6: that is somewhat hilarious! It would be interesting to get to the bottom of this. I’ve looked through all of Whitney’s papers on graph theory (Volume 1 of his collected works is available on Springer), and I’m pretty sure that Theorem 11 of Congruent graphs and the connectivity of graphs must be the correct reference. But who first formulated the result as about ’unique embedding’ rather than ’unique duals’, and if there is any explanation for the proliferation of references except carelessness, remains mysterious.

    Regarding #7: do you agree with the following?

    1) An isomorphism between geometric duals implies an isomorphism of the original graphs which takes boundaries to boundaries. By boundaries here we mean as abstract subgraphs, i.e. we just have the (unordered) set of vertices, the (unordered) set of edges, and the information as to which pair of vertices are the ends of each edge.

    2) An isomorphism between geometric duals defines a bijective correspondence between the faces, and hence between their boundaries.

    It seems to me that 1) and 2) immediately imply that the set of boundaries is sent exactly to the set of boundaries. This property is equivalent to having a planar isotopy (after, if we are working in ℝ 2\mathbb{R}^{2} rather than the sphere, choosing a face to be the outer one).

    If you are not convinced by 1), please let me know! It seems to me to be immediate from the definition of the geometric dual.

    • CommentRowNumber10.
    • CommentAuthorRichard Williamson
    • CommentTimeAug 6th 2017
    • (edited Aug 6th 2017)

    Thank you for thoughts too, Peter! I myself am interested in finite graphs. I am interested in the plane, but, as far as I know, it doesn’t make any essential difference whether we consider the plane or the sphere, in the finite case at least: when working in the plane, one just has to choose an outer face, otherwise there is no difference. I am working with the geometric dual, but again (for finite graphs at least), I believe that the uniqueness of geometric duals is equivalent to the uniqueness of combinatorial duals. In this case, there are at least three notions of what it means for the embeddings to be ’the same’, and all of them are equivalent. I refer you to for example Diestel’s book. One of these is the one I am using in my argument above (face boundaries sent exactly to face boundaries); one is planar isotopy (self-homeomorphism of ℝ 2\mathbb{R}^{2} taking one of the embeddings to the other); and the third is kind of ‘in between’ these.

    As far as I know, Whitney’s theorem does hold for infinite graphs (but I don’t anything about the details, e.g. if there are any changes in what I wrote above for the infinite case), so a counterexample would definitely be interesting in that setting.

    [Edited to remove inaccurate comment.]

    I am not sure exactly what you mean by an infinite double ray, so have not really thought carefully about your proposed counterexample yet. But it sounds like it might not be connected, and I think one should at least require that, because even in the finite case the dual is not so well behaved in the absence of connectedness (e.g. the double dual is not necessarily isomorphic to the original).

  11. Coming back to the historical search for a moment, I think the following paper of Fleischner might be significant: The uniquely embeddable planar graphs. A major point of this paper seems to be define unique embeddability in the way we understand it today; indeed, in the abstract, he suggests that Whitney proved his result (Theorem 11 of the Congruent … paper, as we thought), and then writes the following (his quotation marks).

    In this manner, the term “uniquely embeddable planar graph” was introduced

    In other words, it seems that this paper of Fleischner might be the one which first formulates and proves Whitney’s theorem in its modern form. Fleischner’s paper has very few references, and with one exception they are either to his own papers, Whitney’s, or the book of Harary; and the latter, as far as I can see, does not give any definition of what ’uniqueness’ of embeddings means, or any hint of how to prove such a result, though it does clearly have some other meaning in mind than that of uniqueness of duals. The Mathscinet review is just a copy of the abstract, but the Zentralblatt review seems like it possibly might shed a bit more light: if someone who is fluent in German could take a look, that would be great. I cannot really read German, but as far as I can make out from English and Norwegian cognates, the last part of the second sentence says that the author is not aware of any explicit definition of ’unique embeddability’ having previously been given.

    This situation may partly explain the proliferation of misleading references: what Whitney did prove in a different paper was the equivalence of geometric and combinatorial duals, and since this is key to a geometric interpretation (at an intuitive, non-rigorous level at least) of ’unique embeddability’, it makes sense to cite it (although to do so without citing the Congruent … paper as well is bizarre!).

  12. On a slightly different note, to explain why I am interested in this result, I believe that every link diagram is equivalent (in fact only R2 moves + planar isotopy are needed) to one whose underlying graph is simple and 3-connected. To make it simple, we can just apply R2 moves to insert a couple of crossings into any loop.

    We can clearly make any link diagram connected: just apply R2 moves to connect the components. The idea for 3-connectedness is just to generalise this argument. The key point is that, using R2 moves, we can make as any crossings (i.e. vertices) and edges as we like on the outer face of our link diagram, wherever we like. This means that, wherever we remove the two crossings, we can always ensure that part of the outer face of the original link diagram is in each of the components which we obtain after removing the two crossings.

    And then, as long as two arcs are on the outer face, we can connect them on the original link diagram using a single R2 move (i.e. without creating any other crossings), and there is no way that either of the two created crossings can be used to disconnect the new link diagam (if only one is removed, then the two components which we connected remain connected to one another, and remain connected within themselves, since removing part of an edge cannot disconnect a link component; whilst if both are removed, then we have just removed a couple of edges of our original link diagram, which cannot disconnect it).

    I would be happy to hear whether people feel that this argument seems correct.

    • CommentRowNumber13.
    • CommentAuthorRichard Williamson
    • CommentTimeAug 6th 2017
    • (edited Aug 6th 2017)

    And if it is correct, what we can conclude is that any link diagram is equivalent under R2 moves, planar (ambient) isotopy, and possibly a single reflection, to one which, after choosing a face to be the outer one, has a unique embedding in the plane. This is a powerful fact, as the main difficulty in re-constructing a link diagram from combinatorial data is in recovering the planar embedding. I can explain what use I plan to put it to another time.

    • CommentRowNumber14.
    • CommentAuthorPeter Heinig
    • CommentTimeAug 7th 2017

    (Richard, re 10, small thing

    when working in the plane, one just has to choose an outer face

    You meant to write “when working in the sphere”, right? It seems you simply mistyped here. In the plane, there is a distinguished face. If you compactify to get to the sphere, there no longer is, and then you have to choose one (if a distinguished face is needed).)

    • CommentRowNumber15.
    • CommentAuthorPeter Heinig
    • CommentTimeAug 7th 2017
    • (edited Aug 7th 2017)

    Richard, re

    I am not sure exactly what you mean by an infinite double ray, so have not really thought carefully about your proposed counterexample yet. But it sounds like it might not be connected, and I think one should at least require that, because even in the finite case the dual is not so well behaved in the absence of connectedness

    in 10: “infinite double ray” == intentionally pleonastic synonym for what is usually called “double ray” == the abstract unlabelled simple undirected graph isomorphic to the graph (ℤ,{(i,i+1):i∈ℤ}(\mathbb{Z},\{ (i,i+1)\colon i\in\mathbb{Z} \})

    (cf. p. 204 in Diestel, Graph Theory, 4th ed)

    EDIT: and of course, it is connected, but only 1-connected, i.e., has connectivity 1, which allows it to have ℵ 0\aleph_0-may equivalence-classes of embeddings up to plane isotopy.

    Please note: my example was a little misleading in that

    • one of course need not use infinite spirals to prove that the double day has more than one embedding into the plane up to plane isotopy: to see that, it already suffices to contrast the traditional ℤ\mathbb{Z}-like embedding, which does not have any limit points (in the point-set topology sense of limit point), with the embedding which lets one end of the double ray accumulate to a limit point.

    • it is obvious that there are at least ℵ 0\aleph_0-many equivalence-classes-up-to-plane-isotopy of embeddings of the double ray RR into the plane: one can easily make any prescribed finite set of points of ℝ 2\mathbb{R}^2 into the set of limit points of an embedding R↪ℝ 2R\hookrightarrow\mathbb{R}^2

    • it seems to be that there not more than ℵ 0\aleph_0-many such equivalence classes, yet have not stopped to write a proof

    • the spiral I tried to use for something related to your conjecture, specialized to 2-connected infinite planar graphs (not that if you use graphs of higher connectedness, it is no longer that easy to achieve a prescribed set of limit-points), yet it will not possible for me to work on that for a while.

    • CommentRowNumber16.
    • CommentAuthorPeter Heinig
    • CommentTimeAug 7th 2017
    • (edited Aug 7th 2017)

    [removed]

    • CommentRowNumber17.
    • CommentAuthorPeter Heinig
    • CommentTimeAug 7th 2017

    (Richard, small thing re 11 : it puzzles me a little to read

    planar isotopy (self-homeomorphism of ℝ 2\mathbb{R}^{2} taking one of the embeddings to the other)

    but possibly you are here immediately making use of the fact that within ℝ 2\mathbb{R}^2 (and also within 𝕊 2\mathbb{S}^2 for that matter) there does not exist any closed curve which is not homotopic to a point?

    I am asking since, to me, “planar isotopy” always sounds like a signal for “ambient isotopy”, while the definition you give in parentheses is, while indeed a very usual one in the topological graph theory literature, a stronger(==identifying more embeddings with one another) notion of equivalence of curves.

    So you were using special properties of the genus-0-setting when conflating these two definitions, right?

    )

    • CommentRowNumber18.
    • CommentAuthorRichard Williamson
    • CommentTimeAug 7th 2017
    • (edited Aug 7th 2017)

    You meant to write “when working in the sphere”, right? It seems you simply mistyped here. In the plane, there is a distinguished face. If you compactify to get to the sphere, there no longer is, and then you have to choose one (if a distinguished face is needed).)

    No, I did intend to write ’when working in the plane’. When embedding in ℝ 2\mathbb{R}^{2}, you need to choose the outer face to obtain a uniqueness statement, because different choices of outer face may give embeddings which are not isotopic (in ℝ 2\mathbb{R}^{2}). This is quite intuitive: one cannot make the outside of a planar embedding ’appear on the inside’ via isotopy, but this distinction vanishes in 𝕊 2\mathbb{S}^{2}.

    I am asking since, to me, “planar isotopy” always sounds like a signal for “ambient isotopy”, while the definition you give in parentheses is, while indeed a very usual one in the topological graph theory literature, a stronger(= identifying more embeddings with one another) notion of equivalence of curves.

    This is a good point to clarify. For what I am doing in knot theory, I am indeed interested in the ’ambient isotopy’ notion. This is why I added the possibility of a single reflection in #13. The graph theorists use the definition of planar isotopy that I gave (self-homeomorphism of ℝ 2\mathbb{R}^{2}). It is the same as ambient isotopy except that we might need to apply a single reflection at the end.

    would you please send this review

    Thank you, I will do so this evening unless someone sees it earlier.

    Regarding #15: I will think about this later today.

  19. Richard #9, I agree that (1) and (2) are true, but I think there is an extra step of reasoning that has to be made explicit for a formal proof. Suppose we are given two 3-connected planar maps M 1M_1 and M 2M_2 with underlying graphs G 1=|M 1|G_1 = |M_1| and G 2=|M 2|G_2 = |M_2|, and dual underlying graphs of the dual maps G 1′=|M 1 *|G_1' = |M_1^*| and G 2′=|M 2 *|G_2' = |M_2^*|. If all I have is an isomorphism f:G 1≅G 2f : G_1 \cong G_2, then I know that the boundaries of the faces of M 1M_1 (corresponding to polygons of degree k≥2k\ge 2, since the graph is 3-connected), get mapped to cycle subgraphs of G 2G_2. How do you use the additional fact of an isomorphism g:G 1′≅G 2′g : G_1' \cong G_2' to argue that ff sends faces boundaries of M 1M_1 to face boundaries of M 2M_2, and hence that M 1≅M 2M_1 \cong M_2?

    Re #11: that’s a very interesting find, thank you!

    • CommentRowNumber20.
    • CommentAuthorPeter Heinig
    • CommentTimeAug 7th 2017
    • (edited Aug 7th 2017)

    (Richard, re your request in comment 11, here is the Zentralblatt review, with only little commentary:

    05110 Fleischner, Herbert: The uniquely embeddably planar graphs. Discrete Math. 4, 347-358 (1973).

    [rendition of the German review; for technical reasons done without any attempt to render the umlauts or the Esszett grapheme]

    H. Whitney bewies Anfang der 30er-Jahre, dass fur zwei beliebige Einbettungen eines ebenen, dreifach-zusammenhangenden Graphen deren (kombinatorische) duale Graphen isomorph sind. Diese Tatsache wurde in den folgenden Jahren dahingehend beschrieben, dass man solche ebene Graphen als “eindeutig einbettbar” bezeichnete, ohne (wie es dem Autor der vorliegenden Arbeit scheint) eine explizite Definition der eindeutigen Einbettbarkeit zu geben. In der vorliegenden Arbeit wird ein zusammenhangender, ebener Graph als eindeutig einbettbar definiert, wenn fur zwei beliebige Einbettungen G_1, G_2 dieses Graphen und fur einen beliebigen Isomorphismus J von G_1 auf auf G_2 folgt, das J (bildlich gesprochen) in allen Knoten die zyklische Kantenanordnung unverandert lasst oder genau umdreht (0^+ - bzw. 0^- - Isomorphismus). Es wird dann bewiesen (Theorem 3.3), dass der Zusammenhang von G hochstens zwei ist, wenn G nicht eindeutig einbettbar ist. Also sind die ebenen, dreifach-zusammenhangenden Graphen eindeutig einbettbar (Corollary 3.4). Ausserdem werden funf weitere Homoomorphie-Klassen zusammenhangender, ebener, eindeutig einbettbarer Graphen bestimmt, die alle eindeutig einbettbaren Graphen vom Zusammenhang <3 erfassen (Theorem 3.5.). Es zeigt sich schliesslich, dass fur zwei beliebige Einbettungen G_1,G_2 eines eindeutig einbettbaren Graphen deren (geometrische) duale Graphen isomorph sind, jedoch ist es moglich (und das wird in der Arbeit nicht festgestellt), dass stets die dualen Graphen von G_1 und G_2 isomorph sind, ohne dass der zugrunde gelegte Graph in obigem Sinne eindeutig einbettbar ist. Autorreferat.

    [translation of the above into English; disclaimer: done as accurately as possible, while keeping it natural-sounding; without any warranty; own translation, not from Zentralblatt]

    H. Whitney proved at the beginning of the thirties that for any two embeddings of a planar three-connected graph the two (combinatorial) dual graphs of said embeddings are isomorphic. This fact has been described in the ensuing years by describing planar graphs with the above property to be “uniquely embeddable”, without (or so it seems to the author of the present work) giving an explicit definition of what it means to be uniquely embeddable. In the present work a connected planar graph G is defined to be uniquely embeddable if the following implication holds: if G_1 and G_2 are arbitrary embeddings of G, and if J: G_1 -> G_2 is an arbitrary isomorphism, then J (figuratively speaking) either preserves the cylic ordering of incident edges at each vertex, or J reverses said ordering at each vertex (the former is called 0^+ - , the latter is called 0^- - isomorphism). Then it is proved (Theorem 3.3), that if G is not uniquely embeddable, then the connectivity of G is at most two. Hence the planar, three-connected graphs are uniquely embeddable (Corollary 3.4). Furthermore, five further homeomorphism-classes [Fleischner with ’homeomorphism-class’ of course means ’equivalence class w.r.t. the relation ’there exists a homeomorphism between the two’, since here the author speaks about abstract graphs, for which ’homeomorphism’ in older graph-theoretical literature means precisely that, not the usual topological meaning of ’homeomorphism’; the two usages are, of course, reconcilable by considering geometric realizations of the graph-qua-simplicial-complex] of connected, planar, uniquely embeddably graphs are determined, such that each graph of connectivity <3 which happens to be uniquely embeddable is in one of these classes (Theorem 3.5) [so in a sense, Fleischner completes the classification of uniquely embeddable graphs here]. Finally it turns out that for any two embeddings G_1,G_2 of a uniquely-embeddable graph, their (geometric) dual graphs are isomorphic. Yet it is possible (and this is not decided in the present work), that there is some planar graph G for which the dual graphs of G1 and G2, respectively, are always isomorphic without G being uniquely embeddable in the above sense. Review by the author.

    )

    • CommentRowNumber21.
    • CommentAuthorPeter Heinig
    • CommentTimeAug 7th 2017
    • (edited Aug 7th 2017)

    Richard,

    Re 20 and re

    I cannot really read German, but as far as I can make out from English and Norwegian cognates, the last part of the second sentence says that the author is not aware of any explicit definition of ’unique embeddability’ having previously been given.

    from 11: you were right in your reading: the author says something to the effect that he thinks that an explicit definition, let alone proof, was apparently missing, adding a parenthetical remark stating the obvious (that it might only seem to him to be such).

    The beginning of the review rather clearly questions that it was justified up until Fleischner’s 1973 paper to say that Whitney proved unique embeddability of three-connected planar graphs.

    • CommentRowNumber22.
    • CommentAuthorPeter Heinig
    • CommentTimeAug 7th 2017
    • (edited Aug 7th 2017)

    (Richard, re 15 and re

    Regarding #15: I will think about this later today.

    let me just separate out, for clarity, something of a toy-observation on double-rays and their embeddings, to keep this post short, I do not draw parallels with what you are really interested in:

    • there of course exist finite non-3-connected, and every non-2-connected, planar graphs which nevertheless happen to be uniquely embeddable in the plane (and they were classified by Fleischner in Theorem 3.5 of “The uniquely embeddable planar graphs”). Arguably the simplest such graphs are the finite paths. The toy example I would like to point out in this comment is that

      • the infinite double-ray, in contrast to the finite paths, is not uniquely embeddable into the plane up to plane isotopy; there rather evidently are at least ℵ 0\aleph_0 many isotopy classes of embeddings

    I know that non-tame knots are not quite mainstream knot theory. Just wanted to separate out this observation about double rays (which of course are not paths, not being compact. )

    • CommentRowNumber23.
    • CommentAuthorPeter Heinig
    • CommentTimeAug 7th 2017
    • (edited Aug 7th 2017)

    Richard, it seems useful, to me, to package into a single comment (what I perceive to be) the two conjectures appearing in this thread, that is: yours from e.g. comment 10, and the “possibility” that Fleischner is mentioning in Zentralblatt 05110 (it seems to me that Fleischner’s conjecture does not appear in his paper, only in his review of it)

    For brevity, let us first define the following property of graphs GG:

    • (un.du) for any two embeddings η 0,η 1:G→ℝ 2\eta_0,\eta_1\colon G\rightarrow\mathbb{R}^2 the geometric duals of im(η 0)\mathrm{im}(\eta_0) and im(η 1)\mathrm{im}(\eta_1) are abstractly isomorphic.

    Richard’s conjecture. (R. Williamson; my rendition, based on a some guessing, picking up on something you said about connectedness elsewhere, please correct me if this is not what you are conjecturing).

    • If GG is a finite connected planar geometric graph, and if GG has (un.du), then any embeddings η 0,η 1:G→ℝ 2\eta_0,\eta_1\colon G\rightarrow\mathbb{R}^2 are equivalent w.r.t. ambient isotopy in ℝ 2\mathbb{R}^2.

    Is it this what you are mainly conjecturing?

    Now to the other conjecture (invented a name for further reference)

    Deceptive uniqueness conjecture, or d.u.c. for short(H. Fleischner, Zentralblatt 05110). There exists a finite planar graph GG which has (un.du), yet is not Fleischner-uniquely-embeddable.

    (The latter means that there exist embeddings η 0,η 1:G→ℝ 2\eta_0,\eta_1\colon G\rightarrow\mathbb{R}^2 and there exists at least one abstract isomorphism Φ:AbstractGraph(η 0)→AbstractGraph(η 1)\Phi\colon \mathrm{AbstractGraph}(\eta_0)\rightarrow \mathrm{AbstractGraph}(\eta_1) which neither preverses all the cyclic orderings of incident edges around vertices, nor reverses each such order.

    This is what I think is a reasonably accurate verbal rendition of what is defined in p. 350 of “The uniquely embeddablye planar graphs.

    I in particular do not add in the hypothesis “connected” in d.u.c., because it seems to me that all Fleischner is assuming is having unique geometric duals, and there of course do exist non-connected graphs which do, the trivial example being the disjoint union of two edges.

    Do you agree that this is what Fleischner is sugggesting at the end of Zentralblatt 05110 ?

  24. Richard, I thought a little bit about #12, and I’m confused about the first step:

    On a slightly different note, to explain why I am interested in this result, I believe that every link diagram is equivalent (in fact only R2 moves + planar isotopy are needed) to one whose underlying graph is simple and 3-connected. To make it simple, we can just apply R2 moves to insert a couple of crossings into any loop.

    You are talking about the underlying 4-valent graph of the link diagram, right? Then I can see how you make it loopless this way, but you won’t make it simple because the R2 move itself inserts a 2-cycle (a pair of 4-valent vertices connected by a double bond). Am I misunderstanding something?

  25. The question about the precise relationship between duals and embeddings has been nagging at me, and I want to try to flesh out the idea from #2 that having a geometric dual G *G^* in some sense determines an embedding of GG, even in the non-planar, non-3-connected case. I believe this relationship holds at least for any combinatorial map, i.e., a representation of a 2-cell embedding of a finite, connected graph into a compact oriented surface. I make the following

    Claim: let M 1M_1 and M 2M_2 be combinatorial maps. If |M 1|≅|M 2||M_1| \cong |M_2| and |M 1 *|≅|M 2 *||M_1^*| \cong |M_2^*| then either M 1≅M 2M_1 \cong M_2 or M 1 op≅M 2M_1^{op} \cong M_2, where |M||M| denotes the underlying graph of MM, M *M^* denotes the dual map of MM, and M opM^{op} denotes the opposite map (i.e., mirror image) of MM.

    Proof sketch: consider the canonical triangulation T(M)=(Black,White)T(M) = (Black,White) of a map MM, which subdivides the underlying oriented surface of MM into alternating “black” triangles and “white” triangles, where the color of a triangle is determined by the type of corners encountered going counterclockwise around the triangle (black = vertex-edge-face, white = vertex-face-edge). The canonical triangulation T(M)T(M), and hence MM itself, is entirely described up to isomorphism by the pair of ternary incidence relations Black(v,e,f)Black(v,e,f) and White(v,e,f)White(v,e,f) induced by the black triangles and white triangles.

    Now, suppose we are just given two abstract graphs G v≅|M|G_v \cong |M| and G f≅|M *|G_f \cong |M^*|. Since MM and M *M^* share the same underlying set of edges EE, we can define a ternary incidence relation Gray(v,e,f)Gray(v,e,f) between nodes (vertices) v∈G vv \in G_v, edges e∈Ee \in E, and nodes (faces) f∈G ff \in G_f. Well, this almost determines the canonical triangulation T(M)=(Black,White)T(M) = (Black,White), except that we also have to pick a color for each triangle. But since the canonical triangulation is checkerboard colored (i.e., alternating black and white), this reduces to deciding the color of a single triangle. One of these choices gives us the original map MM, the other gives us the opposite map M opM^{op}.

    • CommentRowNumber26.
    • CommentAuthorRichard Williamson
    • CommentTimeAug 8th 2017
    • (edited Aug 8th 2017)

    Thanks for this Noam, I am very happy and grateful that you are thinking about #12; this is what I am really interested in. I am very grateful for your question: I had completely missed this! You are certainly correct that one will have treat removal of loops and removal of double edges separately. Removal of loops can of course be done using R1 moves as well, but I’d like something which also works for (blackboard) framed link diagrams, hence why I used R2 moves. For removal of double edges: I think I see a way to do this, using R3 moves as well. Moreover, I think that it interacts fine with the argument for obtaining 3-connectedness. I will describe this as soon as I get the chance, probably tomorrow; in the meantime, maybe you see some way to do it as well? I would also be very interested in whether you think the argument for 3-connectedness seems promising, if one disregards the double edge issue (or assumes it can be handled).

  27. I will reply to the earlier messages in the thread as well when I get the chance, over the next few days sometime. Thank you to you both for thinking about this. Just wanted to say especially already thanks very much Peter for the translation, this was very kind of you, and very useful!

  28. We cross-posted; I wrote #26 and #27 before I saw #25. I will enjoy reading #25 and hopefully responding tomorrow.

  29. Richard #26:

    For removal of double edges: I think I see a way to do this, using R3 moves as well. Moreover, I think that it interacts fine with the argument for obtaining 3-connectedness. I will describe this as soon as I get the chance, probably tomorrow; in the meantime, maybe you see some way to do it as well? I would also be very interested in whether you think the argument for 3-connectedness seems promising, if one disregards the double edge issue (or assumes it can be handled).

    I am not sure, but one thing I was wondering about is how/whether your procedure translates under the medial map/Tait graph correspondence to a procedure on signed plane graphs. Does it turn an arbitrary signed plane graph into a 3-connected one?

  30. p.s.: thank you Peter, for the translation #20. If I understand correctly, in the last sentence Fleischner is asking about the implication “unique dual ⇒\Rightarrow unique embedding up to mirror symmetry”. I agree with Richard that this is true, and what I am saying in #25 is that I believe it is a consequence of a more general property that a dual G *G^* of GG determines an embedding of GG up to mirror symmetry, even in the non-planar and non-3-connected (but still finite and oriented) case.

    • CommentRowNumber31.
    • CommentAuthorRichard Williamson
    • CommentTimeAug 10th 2017
    • (edited Aug 10th 2017)

    Here is the promised explanation of how to remove double edges. Suppose that we have one, which looks as follows (one or both of the crossings can have the opposite choice of over-arc, it makes no difference).

         -----
    |     |
--- | --- | ---
    |     |
    |     |

    Then we take any piece of arc, and do the following (it is always possible to find a piece for which one can do it without introducing any further crossings). It requires two R2 moves and a single R3 move.

             ----------
        |          |
------- | ---      |
        |    |     |
--      |    |     |
   |    |    |     |
------- | -------- | ---
   |    |    |     |
   |    |    |     |
    --- | ---      |
        |          |
        |          |

    Now, this certainly removes double edges. Moreover, rather than the procedure I suggested in #12 for obtaining 3-connectedness, one can modify it to use the above trick: drag a piece of an arc on an outer face on one component under a crossing on the other as above. Then we do not have to worry about introducing double edges, and it still can be straightforwardly seen, I believe, that we obtain something 3-connected.

    • CommentRowNumber32.
    • CommentAuthorRichard Williamson
    • CommentTimeAug 10th 2017
    • (edited Aug 10th 2017)

    Regarding #29: thanks for the question, Noam! I have not worked much with signed planar graphs, but, without having thought about it very deeply, I would expect to be able to carry out the same kind of argument, yes.

    Regarding #19: thanks for explaining where you would like more justification. To get that face boundaries go to face boundaries, one might argue as follows. It is immediate from the definition of the dual graph that the edges incident to a vertex of the dual graph correspond exactly, when we take the dual once more and identify the double dual with the original graph, to the edges in the boundary of the corresponding face of the original graph. It is also immediate that the isomorphism of the abstract dual graphs, as with any isomorphism of graphs, takes the set of edges incident to a vertex to the set of edges incident to some vertex. Under the isomorphism of the original graphs induced by the isomorphism of the dual graphs, we then have that a set of boundary edges is taken to a set of boundary edges. But an isomorphism of graphs which takes a set of edges to a set of edges defines an isomorphism of the subgraphs determined by these edges, i.e. takes a face boundary to a face boundary. I don’t see anything missing here from a formal point of view? Here the main ingredient is really that the double dual is isomorphic to the original graph; this is where some geometrical argument is involved. But that we have such an isomorphism (if we assume connectedness) is well-known, of course.

    Still not had a chance to think about the other things.

  33. Yes, I agree your argument in #32/#4 is fine. (I think we’re essentially giving the same argument, basically relying on the fact that the vertex-edge-face incidences are preserved.)

    Re #31: I can sort of see it. Actually, I think it could be useful to view this “throw a piece of arc under” operation as acting on a single crossing:

            |         
----    |     
    |   |        
----    |        
        |        
------- | ------
        |         
        |         
        |       
        |          
        |

    ⇒\Rightarrow

            |         
------- | ---     
        |    |    
--      |    |    
   |    |    |    
------- | ------
   |    |    |     
   |    |    |     
    --- | ---      
        |          
        |

    If you apply this operation once to every crossing + adjacent arc you’ll obtain an isotopic loopless diagram, and if you apply it twice you’ll obtain a simple one. That might not be very efficient, but it reminds me of the way you can turn a general graph into a homeomorphic simple graph through the operation of barycentric subdivision.

    (I haven’t tried to check your argument for 3-connectedness yet, though.)

  34. Thanks very much Noam, that’s a nice idea! As for 3-connectedness, I am not sure that I can make use of it in the way I was originally hoping, but I still think it would be a nice observation if true, probably useful for something.

    (I think we’re essentially giving the same argument, basically relying on the fact that the vertex-edge-face incidences are preserved.)

    I agree, that’s a good way of putting it.

    • CommentRowNumber35.
    • CommentAuthorNoam_Zeilberger
    • CommentTimeAug 17th 2017
    • (edited Aug 17th 2017)

    Hello Richard, Sorry I didn’t get around to checking your 3-connectedness argument, but I think I would need to see it spelled out in more detail. One thing that I don’t quite understand is your reference to the outer face…what if there is some piece of my diagram that is only 2-connected, yet is buried far away from the outer face? (I have in mind a “long subknot”, i.e., a long knot occurring somewhere within the larger diagram, with neither of its two ends incident to the outer face.) If I try to attach it directly to an arc on the outer face via an R2 move, it seems that could violate planarity – is that what you really had in mind? I think it would probably suffice to attach the subdiagram to an arc on one of the inner faces…but I would want to see the transformation and connectivity argument spelled out.

  36. My apologies for the terribly slow response, Noam!

    I think I would need to see it spelled out in more detail.

    Absolutely, I will probably try at some point to write this down carefully.

    what if there is some piece of my diagram that is only 2-connected, yet is buried far away from the outer face?

    If I try to attach it directly to an arc on the outer face via an R2 move, it seems that could violate planarity – is that what you really had in mind?

    This is exactly the main point of difficulty with demonstrating 3-connectedness, it is great that you raise this. The role of the outer face in my argument is precisely intended to address this point. To understand it, let us perhaps return to showing how to make a link connected: this is trivial, because one can just use an R2 move to link any pair of components. The idea for 3-connectedness is to reduce to this case, to the extent that that makes sense. Now, if removing two points disconnects the graph, then we now have at least two components, and we can trivially connect them using an R2 move (or more than one).The problem is that this R2 move may not be able to be carried out on the original knot. But it is trivial to do on the original knot as long the arcs (i.e. on both components) where we are carrying out the R2 move are on an outer face of the original knot. So it remains only to observe that we can arrange the original knot so that part of the original outer face always is on any components which result after removing two points (i.e. there are sufficiently many crossings on the outer face). We also need to make sure that the crossings we add during the R2 moves do not introduce new ways to disconnect the graph or violate simplicity after removing two points, but it seems that this can be arranged too, using the ’slinging under a crossing’ move instead of a plain R2.

1 to 36 of 36

  1.