Timeline for Connected geometric thickness two
Current License: CC BY-SA 4.0
32 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Oct 23, 2023 at 16:06 | history | bounty ended | CommunityBot | ||
| S Oct 23, 2023 at 16:06 | history | notice removed | CommunityBot | ||
| Oct 22, 2023 at 1:43 | comment | added | Jan Nienhaus | If you are happy with an infinite example, I think $\mathbb{Z}^2$ with edges of slopes $(1,0),(0,1),(1,2),(1,3),(2,1),(3,1)$ does the trick. | |
| Oct 20, 2023 at 1:11 | comment | added | Alex Ravsky | @domotorp The closest result which I know is Fig. 3 from the paper Thickness and colorability of geometric graphs (Computational Geometry 56 (2016) 1-18) by Stephane Durocher, Ellen Gethner, Debajyoti Mondal, where are shown "all the three combinatorially different configurations of nine points that support geometric thickness-two drawings of" $K_9$ without an edge. | |
| Oct 20, 2023 at 0:20 | comment | added | Jan Nienhaus | This condition can be seen to be equivalent to requiring that all components of $G_1, G_2$ have at least one edge (i.e. have no isolated points) for all valid decompositions, but I also can't find an example where this seemingly weaker condition seems to hold. | |
| Oct 19, 2023 at 4:18 | comment | added | domotorp | Do you know of any graph that has a unique geometric thickness two embedding? I feel like that could be a good start for a construction. | |
| S Oct 15, 2023 at 14:52 | history | bounty started | Lorenzo Pompili | ||
| S Oct 15, 2023 at 14:52 | history | notice added | Lorenzo Pompili | Draw attention | |
| S Oct 15, 2023 at 13:46 | history | bounty ended | Alex Ravsky | ||
| S Oct 15, 2023 at 13:46 | history | notice removed | Alex Ravsky | ||
| Oct 9, 2023 at 2:32 | comment | added | Alex Ravsky | @quarague Sulanke's nine-color Earth–Moon map has $11$ vertices and $50$ edges, whereas any $11$-vertex graph of geometric thickness two has at most $48$ vertices, see the paper ``On representations of some thickness-two graphs'' (Computational Geometry 13 (1999) 161–171) by Joan P. Hutchinson, Thomas Shermer, and Andrew Vince. | |
| Oct 7, 2023 at 13:22 | comment | added | Alex Ravsky | Unfortunately, it seems that I found the disconnected drawings for all graphs form my answer. So I deleted it and returned the bounty. | |
| S Oct 7, 2023 at 13:20 | history | bounty started | Alex Ravsky | ||
| S Oct 7, 2023 at 13:20 | history | notice added | Alex Ravsky | Draw attention | |
| S Oct 7, 2023 at 12:20 | history | bounty ended | Till | ||
| S Oct 7, 2023 at 12:20 | history | notice removed | Till | ||
| Oct 7, 2023 at 9:48 | answer | added | Alex Ravsky | timeline score: 3 | |
| S Oct 1, 2023 at 15:21 | history | suggested | Lorenzo Pompili | CC BY-SA 4.0 |
I removed parentheses and highlighted more the fact that edges are straight lines, as the term “plane” can also refer to graphs with curved edges.
|
| Oct 1, 2023 at 14:12 | review | Suggested edits | |||
| S Oct 1, 2023 at 15:21 | |||||
| Sep 30, 2023 at 13:52 | answer | added | Lorenzo Pompili | timeline score: 6 | |
| Sep 30, 2023 at 12:16 | history | edited | Wlod AA | CC BY-SA 4.0 |
connected
|
| S Sep 30, 2023 at 10:23 | history | bounty started | Till | ||
| S Sep 30, 2023 at 10:23 | history | notice added | Till | Draw attention | |
| Sep 14, 2023 at 14:27 | history | edited | Till | CC BY-SA 4.0 |
added 66 characters in body
|
| Sep 14, 2023 at 14:26 | comment | added | Till | @quarague: the wikipedia page considers thickness and not geometric thickness of a graph. I do not think that the graph on the Wikipedia page has geometric thickness 2. I did not check the graph carefully though. Thanks for the pointer. | |
| Sep 14, 2023 at 14:22 | comment | added | Till | - Yes, the term plane, means representing edges by segments. Good question. - Clearly, you can find a decomposition of the edges that make the drawing connected. That is easy. The difficult part is to find a graph such that every embedding and decomposition has this property. | |
| Sep 14, 2023 at 13:47 | comment | added | quarague | Did you check whether the Sulanke's nine-color Earth–Moon map on the wikipedia page for graph thickness en.wikipedia.org/wiki/Thickness_(graph_theory) is such an example? | |
| Sep 14, 2023 at 13:34 | comment | added | Peter Taylor | @quarague, by exhaustion no subgraph of $K_6$ serves as an answer. | |
| Sep 14, 2023 at 13:10 | comment | added | quarague | From some doodling, for $K_5$ there exists an embedding and a decomposition such that $G_1$ and $G_2$ are plane and connected. I don't think any decomposition is doable, for example it implies that for every vertex any decomposition needs to asign at least one adjacent edge to each part of the decomposition. | |
| Sep 14, 2023 at 11:51 | comment | added | Ilya Bogdanov | Do you assume that all edges are represented by segments? | |
| Sep 14, 2023 at 11:42 | history | edited | YCor | CC BY-SA 4.0 |
removed capitals from title, changed tag
|
| Sep 14, 2023 at 10:04 | history | asked | Till | CC BY-SA 4.0 |