TOPICS
Search

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"].

GraphThickness

A lower bound for the thickness of a graph is given by

 t(G)>=[m/(3n-6)],
(1)

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.

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 K_n satisfies

 t(K_n)=|_(n+7)/6_|
(2)

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

 t(K_(m,n))=[(mn)/(2(m+n-2))]
(3)

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.

mnr
13174
17215
19296
19477
21256
23759
25297
25599

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

 t(K_(n,n))=|_(n+5)/4_|
(4)

(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

 t(Q_n)=[(n+1)/4]
(5)

(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, Local Crossing Number, Planar Graph

Explore with Wolfram|Alpha

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.Kainen, P. C. "Thickness and Coarseness of Graphs." Abh. Math. Semin. Univ. Hamburg 39, 88-95, 1973.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."Thomassen, C. "Rectilinear Drawings of Graphs." J. Graph Th. 12, 335-341, 1988.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. https://mathworld.wolfram.com/GraphThickness.html

Subject classifications