Skip to main content
5 of 5
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.

Connected geometric thickness two

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.

Till
  • 479
  • 3
  • 9