تسجيل الدخول

تسجيل

Graph Thickness

المؤلف:  Alekseev, V. B. and Gonchakov, V. S

المصدر:  "Thickness of Arbitrary Complete Graphs." Mat. Sbornik 101

الجزء والصفحة:  ...

24-4-2022

4041

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.