# 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$$?

#### Example for $$v=12$$

An example of such a graph with thickness $$2$$ with $$|V|=12$$ is the following.

$$V=\{N,1,2,3,4,5,1’,2’,3’,4’,5’,S\},$$ $$E=\{(v,w)\,|\,v,w\in V,v\neq w\}\setminus\{(N,S),(i,j’)|1\leq i,j\leq 5, j-i= 3\mod 5\}.$$ We note that $$|E|={12\choose 2}-6=60=6|V|-12$$, which is the theoretical upper bound for thickness $$2$$ graphs. We can decompose $$E$$ into $$E=E_1\cup E_2,$$ $$E_1=\{ (N,i)|1\leq i \leq 5\}\cup \{ (S,i’)|1\leq i \leq 5\}\cup\{(i,j),(i’,j’),)\,|\,j-i=1\mod 5\}\cup \{ (i,j’)\,|\,1\leq i,j \leq 5,\,j-i=0\text{ or }1\mod 5\},$$ $$E_2=\{ (N,i’)|1\leq i \leq 5\}\cup \{ (S,i)|1\leq i \leq 5\} \cup\{(i,j),(i’,j’),)\,|\,j-i=2\mod 5\}\cup \{ (i,j’)\,|\,1\leq i,j \leq 5,\,j-i=2\text{ or }4\mod 5\}.$$ Then, $$G_1=(V,E_1),G_2=(V,E_2)$$ are both planar graphs, as they coincide with the vertex-edge scheme of an icosahedron. To see that, you can think of $$N,S$$ as the north and south vertices, while $$A:=\{1,2,3,4,5\},B:=\{1’,2’,3’,4’,5’\}$$ are the two sets of vertices with same latitude, except that in $$G_1$$, the set $$A$$ is in the north emisphere and $$B$$ is in the southern emisphere, and in $$G_2$$ it’s the opposite (and the arrangements of the points in $$A$$ and $$B$$ along the two circles of latitude is different in the two graphs).

So, since $$G_1$$ and $$G_2$$ are planar, the graph has clearly thickness two.

The basic idea is: take a ball, draw $$12$$ vertices on it, and connect them with $$30$$ red edges to form an icosahedron (so that red edges do not intersect). Then, if you are careful enough, you can draw another $$30$$ blue edges, so that all edges (red and blue) connect different pairs of points, and such that blue edges do not cross each other.

There is no such graph on $$11$$ vertices, but for all $$n \geq 12$$, there exists a thickness-$$2$$ graph with $$6n-12$$ edges. Both these results were proved by Boswell and Simpson in Edge-disjoint maximal planar graphs. The proof of existence follows easily by induction using the following theorem of Boswell and Simpson.
Theorem. If $$T_1$$ and $$T_2$$ are edge-disjoint triangulations on the same set of vertices, then each face of $$T_1$$ is vertex-disjoint from at least $$3$$ faces of $$T_2$$.