Timeline for Connected geometric thickness two
Current License: CC BY-SA 4.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 15, 2023 at 14:53 | comment | added | Lorenzo Pompili | Well, I started a new one x) My answer is not worth 100 rep | |
| Oct 15, 2023 at 13:46 | comment | added | Alex Ravsky | The bounty and best regards. | |
| Oct 15, 2023 at 13:46 | history | bounty ended | Alex Ravsky | ||
| Oct 7, 2023 at 10:22 | comment | added | Alex Ravsky | For each natural $n\ge 4$, any $n$-vertex graph of geometric thickness two has at most $6n-18$ edges, see the details in Tony Huynh's answer to the other recent OP bounty question and my comment to it. Also it the referenced paper is posed Question 1, whether for $n>4$ there exists a graph of geometric thickness two on $n$ vertices with either $6n-18$ or $6n-19$ edges. | |
| Oct 7, 2023 at 10:01 | history | edited | Alex Ravsky | CC BY-SA 4.0 |
Fixed a misprint.
|
| Oct 1, 2023 at 22:37 | history | rollback | Lorenzo Pompili |
Rollback to Revision 8
|
|
| Oct 1, 2023 at 16:16 | history | edited | Lorenzo Pompili | CC BY-SA 4.0 |
deleted 10 characters in body
|
| Oct 1, 2023 at 14:39 | history | edited | Lorenzo Pompili | CC BY-SA 4.0 |
added 128 characters in body
|
| Oct 1, 2023 at 14:00 | comment | added | Lorenzo Pompili | @AlexRavsky right, I missed that, thank you. Ok, now I see that your argument works. I am so silly that I did not read the requirement of the edges being straight lines in the question. I edited the answer to sum up the discussion. | |
| Oct 1, 2023 at 13:58 | history | edited | Lorenzo Pompili | CC BY-SA 4.0 |
Just a long comment with somewhat trivial remarks
|
| Oct 1, 2023 at 11:08 | history | edited | Lorenzo Pompili | CC BY-SA 4.0 |
Added Proposition 2
|
| Sep 30, 2023 at 19:51 | history | edited | Lorenzo Pompili | CC BY-SA 4.0 |
added 124 characters in body
|
| Sep 30, 2023 at 19:39 | history | edited | Lorenzo Pompili | CC BY-SA 4.0 |
deleted 42 characters in body
|
| Sep 30, 2023 at 19:26 | history | edited | Lorenzo Pompili | CC BY-SA 4.0 |
added 300 characters in body
|
| Sep 30, 2023 at 19:21 | comment | added | Alex Ravsky | @LorenzoPompili The common vertex embedding is fixed both for $G_1$ and $G_2$, see the beginning of the question. | |
| Sep 30, 2023 at 18:53 | comment | added | Lorenzo Pompili | And if you start from the beginning with a representation in which $E_1’’$ and $E_2’’$ are planar, first of all I am not sure it always exists (that is something I don’t know). But even if it did, it is not guaranteed that the convex hull of the graph has at least three vertices: you could have intersections of edges on the perimeter of the graph, which makes not even clear how to define the convex hull… | |
| Sep 30, 2023 at 18:49 | comment | added | Lorenzo Pompili | @AlexRavsky your idea is very interesting, but I am not fully convinced that your argument works. In particular, $E’\cup E’’_i$ is not necessarily planar as it might seem. Sure, $E’$ is the outer perimeter in some representation of the graph, and $E_i’’$ is planar, so has no self-intersections in some other representation of the graph. But if the representations do not coincide, the union could be not planar. For instance, take $K_5$, and take any representation where it has 3 edges as perimeter. If you remove those three edges, the remaining graph has self-intersections, but it is planar. | |
| Sep 30, 2023 at 17:20 | comment | added | Alex Ravsky | I think the main idea of the answer cannot provide a required example. Indeed, suppose for a contradiction that $E'$ is the set of the edges of the convex hull of the vertex set of the graph and $E''$ is the set of the remaining edges of the graph. Note that $|E'|\ge 3$. Let $E''=E''_1\cup E''_2$ be decomposition of $E''$ into the edges of the respective graphs. Then $|E'|+|E''_i|\le 3v-6$ for each $i\in\{1,2\}$. Thus $$|E|\le |E'|+|E''_1|+|E''_2|\le 2(3v-6)-3=6v-15<6v-14=|E|,$$ a contradiction. | |
| Sep 30, 2023 at 16:33 | comment | added | Lorenzo Pompili | I think it is extremely unclear whether you can do that without increasing the thickness. | |
| Sep 30, 2023 at 15:37 | comment | added | Fabius Wiesner | But we need to check if the geometric thickness of that graph is also two. | |
| Sep 30, 2023 at 15:28 | comment | added | Fabius Wiesner | If you take from the above cited Wikipedia page about graph thickness, the graph there described related to "Sulanke's nine-color Earth–Moon map", i.e. the join of a 6-vertex complete graph and 5-vertex cycle graph, which has thickness two, then add two edges to the 5-vertex cycle graph, by which the thickness doesn't change, you have $v=11$ and $e = 6v-14=52$ as desired. | |
| Sep 30, 2023 at 14:07 | history | edited | Lorenzo Pompili | CC BY-SA 4.0 |
added 13 characters in body
|
| Sep 30, 2023 at 13:52 | history | answered | Lorenzo Pompili | CC BY-SA 4.0 |