Connected geometric thickness two

Question

A graph $G = (V,E)$ has geometric thickness two if there exists an embedding $\varphi: V \rightarrow \mathbb{R}^2$ and a decomposition $E = E_1\cup E_2$ such that $G_1 = (V,E_1)$ and $G_2 = (V,E_2)$ are both plane with this embedding. Here by “plane” I mean that all edges are drawn as straight line segments which do not intersect.

For instance, it is easy to see that $K_5$ has thickness two.

I am looking for a connected graph $G$ with geometric thickness two such that for any valid embedding and any valid decomposition, both graphs $G_1$ and $G_2$ are connected.

Answer 1

Disclaimer. This answer does not solve the problem. I decided it is probably more useful to keep my answer here, but please know it is just a long comment.

Notation. For a graph $(V,E)$, we call $e=|E|, v=|V|$.

---

In a planar graph, we have a maximum number of edges: $e\leq 3v-6$ if $v\geq 3$. Thus, for a graph of thickness $2$, we have the trivial upper bound $$ e\leq 6v-12. $$

Proposition 1. Let $(V,E)$ be a graph with thickness* $2$ and such that $e\in\{6v-14,6v-13,6v-12\}$. Then for any decomposition $E=E_1\cup E_2$ such that the graphs $(V,E_1),(V,E_2)$ are planar, the two are also connected.

*Remark. As you can check from the proof, the proposition is true for both the geometric thickness and the “normal” thickness.

Proof. To see that, assume you decompose $E=E_1\cup E_2$. Since $(V,E_i)$ must be planar graphs (and $v\geq 5$), we have $$|E_i|\leq 3|V|-6$$ Since $|E|\ge 6|V|-14$ and $|E_1|+|E_2|=|E|$, it follows that $$ |E_i|\geq 3|V|-8. $$ Now, I claim that the two subgraphs cannot be disconnected. In fact, to any disconnected planar graph with $v\geq 4$ you can add at least three edges while still keeping it planar (the main reason is that any face of a planar graph has at least three vertices). But if you add three edges to $E_i$ you make it exceed the maximum number of edges for a planar graph, so both $(V,E_1)$ and $(V,E_2)$ must be connected.

Note that such a graph would require at least $v\geq 11$, since for $6v-14\leq {n\choose 2}\iff n\geq 11 \text{ or } n\leq 2$.

---

Edit 1. Thanks to the nice remark of Alex Ravsky, we know that such a graph cannot exist with geometric thickness $2$, although graphs with “normal” thickness $2$ exist with $e=6v-12$ (or at least, I know of such an example for $v=12$). In particular we can say something about a graph like the one in Proposition 1.

Lemma 2. Assume $(V,E)$ is a graph with $e=6v-12-c$, $c\in\mathbb N$. Then, in any representation of the graph in $\mathbb R^2$ where edges are not necessarily straight lines and such that $E$ can be written as a disjoint union of planarly embedded graphs, the number of edges $e’$ that do not intersect with any other edge is at most $c$.

Proof. As from the comment of Alex Ravsky, call $E’$ the set of edges that do not cross other edges, and call $E’’$ the set of remaining edges. Then write $E’’=E’’_1\cup E’’_2$ such that $E_i’’$ are planarly embedded. Then, $E’\cup E’’_i$ are also planarly embedded, in particular $$ |E’’_i|+|E’|\leq 3|V|-6. $$ This leads to $$ |E|+|E’|\leq 6|V|-12, $$ which proves the Proposition.

Corollary 3. Any graph with geometric thickness $2$ satisfies $e\leq 6v-15$.

Proof. The convex hull of the graph cannot have edges that intersect with other edges, and it is made of at least $3$ edges.

Answer 2

I tried to find a required example, but failed (I share my findings below). Nevertheless, it seems rather strange to me if there is no such example, so I hope that it can be constructed.

A natural idea is to look for rather dense graphs of geometric thickness two. Density of the latter graphs was studied in [HSV]. There is shown that for each natural $n\ge 4$, any $n$-vertex graph of geometric thickness two has at most $6n−18$ edges. On the other hand, according to Theorem 1 from [DGM], for each $n\ge 9$ there exists an $n$-vertex graph of geometric thickness two with $6n−19$ edges.

We start from complete graphs. The graph $K_9$ has thickness three [BHK, T] and the biggest order of a complete graph of geometric thickness two is eight, see Theorem 2.1 from [DEH] or [HSV, 2.1]. But the graph $K_8$ has the disconnected drawing, see Fig. 2 from [HSV]. Moreover, as far as I can see at Fig. 3 from [DGM], even the complete graph $K_9$ minus one edge has the disconnected drawing.

The complete bipartite graphs of geometric thickness two were less promising candidates, because they are rather sparse. Indeed, it is easy to construct the disconnected drawing of the graph $K_{4,k}$ for any natural $k$ and the disconnected drawing of the graph $K_{6,6}$ is shown at Figure 2 from [DEH].

References

[BHK] J. Battle, F. Harary, Y. Kodama, Every planar graph with nine points has a nonplanar complement, Bull. Amer. Math. Soc. 68 (1962) 569–571.

[Bei] L.W. Beineke Biplanar Graphs: A Survey, Computers Math.Applic. 34:11 (1997) 1-8.

[DEH] Michael B. Dillencourt, David Eppstein, Daniel S. Hirschberg, Geometric Thickness of Complete Graphs, Journal of Graph Algorithms and Applications 4:3 (2000) 5-17.

[DGM] Stephane Durocher, Ellen Gethner, Debajyoti Mondal, Thickness and colorability of geometric graphs, Computational Geometry 56 (2016) 1-18.

[E] David Eppstein, Separating Thickness from Geometric Thickness, arXiv, 2003.

[HSV] Joan P. Hutchinson, Thomas Shermer, Andrew Vince, On representations of some thickness-two graphs, Computational Geometry 13 (1999) 161–171.

[Tut] W.T. Tutte, On the non-biplanar character of the complete $9$-graph, Canad. Math. Bull. 6 (1963) 319–330.