Skip to main content
2 of 5
removed capitals from title, changed tag
YCor
  • 63.9k
  • 5
  • 187
  • 286

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.

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