Graph Thickness


The thickness (or depth) t(G) (Skiena 1990, p. 251; Beineke 1997) or theta(G) (Harary 1994, p. 120) of a graph G is the minimum number of planar edge-induced subgraphs P_i of F needed such that the graph union  union _iP_i=G (Skiena 1990, p. 251).

The thickness of a planar graph G is therefore t(G)=1, and the thickness of a nonplanar graph G satisfies t(G)>=2. 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


where m is the number of edges, n>=3 is the number vertices, and [x] is the ceiling function (Skiena 1990, p. 251). The example above shows a decomposition of the complete graph K_9 into three planar subgraphs. This decomposition is minimal, so t(K_9)=3, in agreement with the bound t(K_9)>=[36/(3·9-6)]=2.

The thickness of a complete graph K_n satisfies


except for t(K_9)=t(K_(10))=3 (Vasak 1976, Alekseev and Gonchakov 1976, Beineke 1997). For n=1, 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 K_(m,n) is given by


except possibly when m and n are both odd and, taking m<n, there exists an even integer r with n=|_r(m-2)/(m-r)_| (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.


According to Beineke (1997), the only subset of exceptional bipartite indices for m<30 are K_(19,29), K_(19,47), K_(23,27), K_(25,59), and K_(29,129).

The thickness of K_(n,n) is therefore given by


(Harary 1994, p. 121), which for n=1, 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 Q_n is given by


(Harary 1994, p. 121), which for n=1, 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


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 K_(34) et K_(40)." 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.

Referenced on Wolfram|Alpha

Graph Thickness

Cite this as:

Weisstein, Eric W. "Graph Thickness." From MathWorld--A Wolfram Web Resource.

Subject classifications