Graph Thickness

The graph thickness (or depth) (Skiena 1990, p. 251; Beineke 1997) or (Harary 1994, p. 120) of a simple graph is the least positive number of planar spanning subgraphs of whose 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 graphs (i.e., that has thickness 1 or 2) is said to be a biplanar graph (Beineke 1997).

Computing the thickness of a graph is an NP-hard problem; deciding whether its thickness is at most 2 is an NP-complete problem (Mansfield 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 of 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 , although the general lower bound gives only .

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).

For , the thickness of a complete graph satisfies

(2)

except for (Alekseev and Gonchakov 1976, Vasak 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 graph has thickness 1. For positive integers with , the thickness of a complete bipartite graph is given by

(3)

except possibly when and are both odd and, taking , there exists a positive 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), where is the floor function. The smallest pairs satisfying this exceptional condition 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

Poranen and Mäkinen (2005) resolved the previously unknown cases with and by finding planar decompositions attaining the general formula above.

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, indexed by ).

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 A008621).

A number of variations of graph thickness such as outerplanar thickness, arboricity, book thickness, and toroidal thickness have also been introduced (Beineke 1997).