Graph Thickness

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 .

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

REFERENCES

Alekseev, V. B. and Gonchakov, V. S. "Thickness of Arbitrary Complete Graphs." Mat. Sbornik 101, 212-230, 1976.

Beineke, L. W. "Biplanar Graphs: A Survey." Computers Math. Appl. 34, 1-8, 1997.

Beineke, L. W. and Harary, F. "On the Thickness of the Complete Graph." Bull. Amer. Math. Soc. 70, 618-620, 1964.

Beineke, L. W. and Harary, F. "The Thickness of the Complete Graph." Canad. J. Math. 17, 850-859, 1965.

Beineke, L. W.; Harary, F.; and Moon; J. W. "On the Thickness of the Complete Bipartite Graph." Proc. Cambridge Philos. Soc. 60, 1-6, 1964.

Harary, F. "Covering and Packing in Graphs, I." Ann. New York Acad. Sci. 175, 198-205, 1970.

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 120-121, 1994.

Harary, F. and Palmer, E. M. Graphical Enumeration. New York: Academic Press, p. 225, 1973.

Harary, F. and Palmer, E. M. "A Survey of Graph Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam: North-Holland, pp. 259-275, 1973.

Hearon, S. M. "Planar Graphs, Biplanar Graphs and Graph Thickness." Master of Arts thesis. San Bernadino, CA: California State University, San Bernadino, 2016.

Mansfeld, A. "Determining the Thickness of a Graph is NP-Hard." Math. Proc. Cambridge Philos. Soc. 93, 9-23, 1983.

Meyer, J. "L'épaisseur des graphes completes  et ." J. Comp. Th. 9, 1970.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 251, 1990.

Sloane, N. J. A. Sequences A124156, A128929, and A144075 in "The On-Line Encyclopedia of Integer Sequences."Tutte, W. T. "The Thickness of a Graph." Indag. Math. 25, 567-577, 1963.

Vasak, J. M. "The Thickness of the Complete Graph." Not. Amer. Math. Soc. 23, A-479, 1976.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 261, 2000.