Thickness (graph theory)

In graph theory, the thickness of a graph $G$ is the minimum number of planar graphs into which the edges of $G$ can be partitioned. That is, if there exists a collection of $k$ planar graphs, all having the same set of vertices, such that the union of these planar graphs is $G$ , then the thickness of $G$ is at most $k$ . In other words, the thickness of a graph is the minimum number of planar subgraphs whose union equals to graph $G$ .

Thus, a planar graph has thickness 1. Graphs of thickness 2 are called biplanar graphs. The concept of thickness originates in the 1962 conjecture of Frank Harary: For any graph on 9 points, either itself or its complementary graph is non-planar. The problem is equivalent to determining whether the complete graph $K 9$ is biplanar (it is not, and the conjecture is true). A comprehensive survey on the state of the arts of the topic as of 1998 was written by Petra Mutzel, Thomas Odenthal and Mark Scharbrodt.

The thickness of the complete graph on $n$ vertices, $K n$ , is

except when $n = 9, 10$ for which the thickness is three.

With some exceptions, the thickness of a complete bipartite graph $K a,b$ is generally:

Every forest is planar, and every planar graph can be partitioned into at most three forests. Therefore, the thickness of any graph $G$ is at most equal to the arboricity of the same graph (the minimum number of forests into which it can be partitioned) and at least equal to the arboricity divided by three. The thickness of $G$ is also within constant factors of another standard graph invariant, the degeneracy, defined as the maximum, over subgraphs of $G$ , of the minimum degree within the subgraph. If an $n$ -vertex graph has thickness t then it necessarily has at most $t (3 n - 6)$ edges, from which it follows that its degeneracy is at most $6 t - 1$ . In the other direction, if a graph has degeneracy $D$ then it has arboricity, and thickness, at most $D$ .

...
Wikipedia