Timeline for Can a 3-regular non-1-planar graph be constructed?
Current License: CC BY-SA 4.0
35 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 1, 2023 at 1:53 | comment | added | Licheng Zhang | Does the claim that every edge in the Desargues graph is in a loop of length 5 came from en.wikipedia.org/wiki/Desargues_graph? Is the Desargues graph we are discussing the same? | |
| Feb 28, 2023 at 14:42 | comment | added | Licheng Zhang | oh, I will check. | |
| Feb 28, 2023 at 14:10 | comment | added | user44143 | Thanks, that clarifies things, but it clarifies that neither of the first two graphs pictured here is the Desargues graph, since they have no loops of length 5, while every edge in the Desargues graph is in a loop of length 5. | |
| Feb 28, 2023 at 12:10 | comment | added | Licheng Zhang | @MattF. See the new editor's post | |
| Feb 28, 2023 at 12:09 | history | edited | Licheng Zhang | CC BY-SA 4.0 |
added 28 characters in body
|
| Feb 27, 2023 at 20:41 | answer | added | Agelos | timeline score: 5 | |
| Feb 27, 2023 at 3:16 | comment | added | Licheng Zhang | I understand your concern. I drew this graph myself using yEd, and it may not be easy to see if it's a Desargues graph, Please check the updated post. | |
| Feb 27, 2023 at 3:14 | history | edited | Licheng Zhang | CC BY-SA 4.0 |
added 194 characters in body
|
| Feb 27, 2023 at 3:00 | comment | added | Licheng Zhang | @MattF. I am sorry. Is this another separate qustion? | |
| Feb 27, 2023 at 2:54 | comment | added | user44143 | Can you color your version of the Desargues graph so each color is a loop of ten vertices? That would allow an easy verification of its being the Desargues graph, which would be difficult now. | |
| Feb 27, 2023 at 1:55 | history | edited | Licheng Zhang | CC BY-SA 4.0 |
added 169 characters in body
|
| Feb 27, 2023 at 1:52 | comment | added | Licheng Zhang | I'm sorry, you're right. Thank you for reminding me. | |
| Feb 27, 2023 at 1:39 | comment | added | Sam Hopkins | @lcz: You did misunderstand me. I merely pointed out that your description "The following embedding is from Wikipedia and it almost has a 1-planar embedding, except for one edge that will cross twice." of that drawing of the graph seems wrong to me: it looks like 3 of the edges will cross twice, not just one edge. | |
| Feb 27, 2023 at 1:32 | comment | added | Licheng Zhang | @SamHopkins Are you saying that you have found a 1-planar drawing of Coxeter graph? Did I misunderstand? | |
| Feb 26, 2023 at 23:23 | comment | added | user44143 | @SamHopkins, you are correct | |
| Feb 26, 2023 at 21:24 | comment | added | Sam Hopkins | @MattF. but in fact mustn’t all three of the connections cross the other two? So really there are three edges with > 1 crossing in this picture? Maybe I’m missing something obvious… | |
| Feb 25, 2023 at 11:32 | vote | accept | Licheng Zhang | ||
| Feb 24, 2023 at 2:33 | comment | added | user44143 | @GerryMyerson, each point on the outside connects to its polar opposite, and one of those three connections must cross the other two. | |
| Feb 24, 2023 at 1:25 | comment | added | Gerry Myerson | That last diagram – I don't see any edge with more than one crossing – is something missing? | |
| Feb 23, 2023 at 2:23 | history | edited | Licheng Zhang | CC BY-SA 4.0 |
added 57 characters in body
|
| Feb 22, 2023 at 23:38 | history | edited | Licheng Zhang | CC BY-SA 4.0 |
added 8 characters in body
|
| Feb 22, 2023 at 19:46 | history | became hot network question | |||
| Feb 22, 2023 at 19:08 | comment | added | Roland Bacher | A small complaint: $1$-planarity can be explained in a sentence or two and is not a well-known notion outside the graph-theory community. I would have liked to have this definition (I looked it up in Wikipedia and I am probably not alone). Questions should be as self-contained as possible. (I am of course not asking for all definitions in very technical domains but it is nice to have questions understandable with almost no background). | |
| Feb 22, 2023 at 18:47 | answer | added | Boris Bukh | timeline score: 16 | |
| Feb 22, 2023 at 14:59 | comment | added | user44143 | Mathworld’s middle two images of the Desargues graph are 6-crossings with more symmetry, and maybe varying one of them can give a 1-planar 6-crossing too: mathworld.wolfram.com/DesarguesGraph.html | |
| Feb 22, 2023 at 14:19 | comment | added | Jukka Kohonen | (In fact the cycle and diagonals is the Möbius ladder, I had a vague recollection but did not remember the name at first.) | |
| Feb 22, 2023 at 14:05 | history | edited | Licheng Zhang | CC BY-SA 4.0 |
added 19 characters in body
|
| Feb 22, 2023 at 13:50 | history | edited | Licheng Zhang | CC BY-SA 4.0 |
added 286 characters in body
|
| Feb 22, 2023 at 13:29 | comment | added | Jukka Kohonen | @Fedor, it is: if you have $2k$ vertices, arrange them in two rows, $1$ to $k$ on top and $k+1$ to $2k$ on bottom. The main diagonals are vertical edges connecting the rows. The cycle edges are horizontal, except the two edges $(1,2k)$ and $(k,k+1)$ which can be drawn around, with one crossing. | |
| Feb 22, 2023 at 12:32 | comment | added | Fedor Petrov | Is a long cycle plus main diagonals 1-planar? | |
| Feb 22, 2023 at 12:17 | comment | added | Licheng Zhang | That's amazing! The problem I think about has already been studied by someone else 10 years ago. | |
| Feb 22, 2023 at 12:03 | answer | added | Joseph O'Rourke | timeline score: 4 | |
| Feb 22, 2023 at 12:02 | comment | added | Peter Taylor | 11011110.github.io/blog/2014/05/11/cubic-1-planarity.html isn't an answer, but suggests some candidates. | |
| Feb 22, 2023 at 11:52 | history | edited | Licheng Zhang | CC BY-SA 4.0 |
added 9 characters in body
|
| Feb 22, 2023 at 11:44 | history | asked | Licheng Zhang | CC BY-SA 4.0 |