How to check if a graph is biplanar (thickness =2)?

Question

Given a graph G how does one check if it can be decomposed into 2 planar graphs other than enumeration.

Note: my given graph has 52 edges and 11 nodes.

Quick edit: the graph has an edge from 4 to 1*

Answer 1

Lemma:

The thickness of $K_n$ is $\lfloor\frac{n+7}{6}\rfloor$ when $n\neq 9,10$ and for cases $n=9,10$ it is $3$.

So if there exists a $K_a$ with $a\geq 9$ in your graph (lets call it $G$), that subgraph has a thickness of at least $3$, so $G$ has a thickness of al least $3$

So for your graph to have a thickness of $2$, it must not have any $K_9$s as subgraphs. Using Turan's theorem, the maximum number of edges of a graph with $11$ vertices which is $K_9-$free is $52$ and if this bound is touched by some graph, it is the Turan graph $T(11,8)$.

Thus, your graph does not have a thickness of $2$ if it is not the Turan graph. If your graph is the Turan graph $T(11,8)$, then observe that it doesnt actually have $52$ edges so again, there is a $K_9$, so your graph has a thickness of at least $3$.

So you graph has a thickness $\geq 3$.

Some closing remarks:

It is NP-hard to compute the thickness of a given graph, and NP-complete to test whether the thickness is at most two.

It is pretty hard to just test the thickness of a graph, as cited above from Wikipedia, especially if you do not have the graph and only the number of vertices and edges are given.