Timeline for Smallest planar graph with two non-homoemorphic plane embeddings?
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 10, 2017 at 18:25 | review | Close votes | |||
| Nov 12, 2017 at 2:15 | |||||
| Nov 10, 2017 at 15:43 | comment | added | YCor | @NoamZeilberger yes I was aware of this (I read the discussion!). | |
| Nov 10, 2017 at 14:46 | comment | added | Noam Zeilberger | @RossDuncan: by the way, Jackson and Visentin's "An Atlas of the Smaller Maps in Orientable and Nonorientable Surfaces" is also a handy reference! | |
| Nov 10, 2017 at 14:45 | comment | added | Noam Zeilberger | @YCor: you are right that the 1 vertex map with two self-loops also has two different embeddings into the plane (one where the outer face has degree 2, one where it has degree 1). Both this example and the one bridge + one loop example correspond to a single embedding into the sphere (where there is no distinguished outer face), but if you add an extra edge (either a bridge or a loop) then you can get different embeddings on the sphere as well (to answer Ross's last question). | |
| Nov 10, 2017 at 14:41 | comment | added | YCor | If "smallest" is first in terms of the rank of the fundamental group (so the smallest graphs are trees) and then by the numbers of vertices, then the smallest with 2 non-equivalent planar embeddings is a tree of 7 vertices made of one "root" with 2 branches of size 2 and 2 branches of size 1. | |
| Nov 10, 2017 at 14:36 | comment | added | YCor | What about 1 vertex with two self-loops? | |
| Nov 10, 2017 at 14:17 | comment | added | Noam Zeilberger | Hello Ross! You might also have a look at Tutte's census paper, in particular Figures 3 and 4. Figure 3 shows the nine different rooted planar embeddings of the four two-edge graphs. If you consider unrooted embeddings into the plane, then the two-vertex graph with one bridge and one loop still has two different embeddings. | |
| Nov 10, 2017 at 14:17 | comment | added | Ross Duncan | Thanks everyone for the comments: if someone writes up an answer I will accept it. | |
| Nov 10, 2017 at 14:13 | comment | added | Dima Pasechnik | if you allow non-simple graphs, the triangle can be degenerate (i.e. two parallel edges, or even a loop --- if loops are allowed) | |
| Nov 10, 2017 at 14:12 | comment | added | Ben Barber | If we don't have to be simple, then a double edge will serve in place of a triangle. | |
| Nov 10, 2017 at 14:11 | comment | added | მამუკა ჯიბლაძე | For the sphere, take the triangle with two extra edges, pointing into the same, resp. different hemispheres | |
| Nov 10, 2017 at 14:10 | comment | added | მამუკა ჯიბლაძე | A triangle with an extra edge pointing in, resp. out? I don't think one can do better... | |
| Nov 10, 2017 at 13:56 | history | edited | Ross Duncan | CC BY-SA 3.0 |
Generalised the labelling condition to something more accurate.
|
| Nov 10, 2017 at 13:50 | comment | added | Ross Duncan | Hi Ben - thanks for this comment. Staring at the example for a few minutes I guess the answer is "yes" -- which is good to know, but I'm going to generalise the question include to the labelled and unlabelled vertices. (In my application, distinct vertices might have the same label.) | |
| Nov 10, 2017 at 13:31 | comment | added | Ben Barber | Does labelling the vertices mean that two different embeddings of $K_4$ in the plane are non-homeomorphic? | |
| Nov 10, 2017 at 13:26 | history | asked | Ross Duncan | CC BY-SA 3.0 |