The thickness (or depth) (Skiena 1990, p. 251; Beineke 1997) or (Harary 1994, p. 120) of a graph is the minimum number of planar edge-induced subgraphs of needed such that the graph union (Skiena 1990, p. 251).
The thickness of a planar graph is therefore , and the thickness of a nonplanar graph satisfies . A graph which is the union of two planar graph (i.e., that has thickness 1 or 2) is said to be a biplanar graph (Beineke 1997).
Determining the thickness of a graph is an NP-complete problem (Mansfeld 1983, Beineke 1997). Precomputed thicknesses for many small named or indexed graphs can be obtained in the Wolfram Language using GraphData[graph, "Thickness"].
A lower bound for the thickness of a graph is given by
(1)
|
where is the number of edges, is the number vertices, and is the ceiling function (Skiena 1990, p. 251). The example above shows a decomposition of the complete graph into three planar subgraphs. This decomposition is minimal, so , in agreement with the bound .
It follows from Brooks' theorem that the thickness of a graph is at most one more than the graph's local crossing number (Kainen 1973, Thomassen 1988).
The thickness of a complete graph satisfies
(2)
|
except for (Vasak 1976, Alekseev and Gonchakov 1976, Beineke 1997). For , 2, ..., the thicknesses are therefore 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, ... (OEIS A124156).
The thickness of a complete bipartite graph is given by
(3)
|
except possibly when and are both odd and, taking , there exists an even integer with (Beineke et al. 1964; Harary 1994, p. 121; Beineke 1997, where the ceiling in the exceptional condition given by Beineke 1997 has been corrected to a floor). The smallest such exceptional values are summarized in the following table.
13 | 17 | 4 |
17 | 21 | 5 |
19 | 29 | 6 |
19 | 47 | 7 |
21 | 25 | 6 |
23 | 75 | 9 |
25 | 29 | 7 |
25 | 59 | 9 |
According to Beineke (1997), the only subset of exceptional bipartite indices for are , , , , and .
The thickness of is therefore given by
(4)
|
(Harary 1994, p. 121), which for , 2, ... give the values 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, ... (OEIS A128929).
Finally, the thickness of a hypercube graph is given by
(5)
|
(Harary 1994, p. 121), which for , 2, ... give the values 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, (OEIS A144075).
A number of variations of graph thickness such as outerplanar thickness, arboricity, book thickness, and toroidal thickness have also been introduced (Beineke 1997).