Skip to main content
2 of 6
The example I showed before was wrong

Sharp upper bound of the number of edges for graphs of thickness two

A graph $G=(V,E)$ has thickness $2$ if $E$ can be written as a disjoint union $E=E_1\cup E_2$ so that $G_1:=(V,E_1),G_2:=(V,E_2)$ are planar graphs. For instance, $K_5$ has thickness $2$. It is known that to have thickness $2$, the graph must satisfy $v\geq 5$, and there is an easy upper bound to the number of edges: $$ e\leq 6v-12. $$

Note also that, if $v\geq 5$, $e=6v-12$ implies that $$ v\geq 11. $$

My question is: is the sharp upper bound on the number of edges for a graph with thickness $2$ and number of vertices $v$ known for every $v$? In particular, are there graphs $(V,E)$ with thickness two such that $e=6v-12$ for any finite set $v$ of size $v\geq 11$?

I thought about this question reading this post. Be aware though that in that post they use a different notion of thickness.