TOPICS

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

## See also

Biplanar Graph, Graph Coarseness, Planar Graph

## Explore with Wolfram|Alpha

More things to try:

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

Graph Thickness

## Cite this as:

Weisstein, Eric W. "Graph Thickness." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GraphThickness.html