Skip to main content
3 of 5
added 66 characters in body
Till
  • 479
  • 3
  • 9

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. (Plane means that all edges are drawn as straight line segments.)

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

I am looking for a 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