Geodesic
The Thickness of Amalgamations and Cartesian Product of Graphs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 561-572.

Voir la notice de l'article provenant de la source Library of Science

The thickness of a graph is the minimum number of planar spanning subgraphs into which the graph can be decomposed. It is a measurement of the closeness to the planarity of a graph, and it also has important applications to VLSI design, but it has been known for only few graphs. We obtain the thickness of vertex-amalgamation and bar-amalgamation of graphs, the lower and upper bounds for the thickness of edge-amalgamation and 2-vertex-amalgamation of graphs, respectively. We also study the thickness of Cartesian product of graphs, and by using operations on graphs, we derive the thickness of the Cartesian product Kn □ Pm for most values of m and n.
Keywords: thickness, amalgamation, Cartesian product, genus 
@article{DMGT_2017_37_3_a4,
     author = {Yang, Yan and Chen, Yichao},
     title = {The {Thickness} of {Amalgamations} and {Cartesian} {Product} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {561--572},
     publisher = {mathdoc},
     volume = {37},
     number = {3},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a4/}
}
TY  - JOUR
AU  - Yang, Yan
AU  - Chen, Yichao
TI  - The Thickness of Amalgamations and Cartesian Product of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 561
EP  - 572
VL  - 37
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a4/
LA  - en
ID  - DMGT_2017_37_3_a4
ER  - 
%0 Journal Article
%A Yang, Yan
%A Chen, Yichao
%T The Thickness of Amalgamations and Cartesian Product of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 561-572
%V 37
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a4/
%G en
%F DMGT_2017_37_3_a4
Yang, Yan; Chen, Yichao. The Thickness of Amalgamations and Cartesian Product of Graphs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 561-572. http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a4/

[1] A. Aggarwal, M. Klawe and P. Shor, Multilayer grid embeddings for VLSI, Algorithmica 6 (1991) 129–151. doi:10.1007/BF01759038

[2] S. Alpert, The genera of amalgamations of graph, Trans. Amer. Math. Soc. 178 (1973) 1–39. doi:10.1090/S0002-9947-1973-0371698-X

[3] V.B. Alekseev and V.S. Gončhakov, The thickness of an arbitrary complete graph, Math. Sbornik. 30 (1976) 187–202. doi:10.1070/SM1976v030n02ABEH002267

[4] K. Asano, On the genus and thickness of graphs, J. Combin. Theory Ser. B 43 (1987) 287–292. doi:10.1016/0095-8956(87)90004-9

[5] J. Battle, F. Harary, Y. Kodama and J.W.T. Youngs, Additivity of the genus of a graph, Bull. Amer. Math. Soc. 68 (1962) 565–568. doi:10.1090/S0002-9904-1962-10847-7

[6] L.W. Beineke and F. Harary, The thickness of the complete graph, Canad. J. Math. 17 (1965) 850–859. doi:10.4153/CJM-1965-084-2

[7] L.W. Beineke, F. Harary and J.W. Moon, On the thickness of the complete bipartite graph, Math. Proc. Cambridge Philos. Soc. 60 (1964) 1–5. doi:10.1017/S0305004100037385

[8] M. Behzad and S.E. Mahmoodian, On topological invariants of the product of graphs, Canad. Math. Bull. 12 (1969) 157–166. doi:10.4153/CMB-1969-015-9

[9] J.A. Bondy and U.S.R.Murty, Graph Theory (Springer, 2008).

[10] J.E. Chen, S.P. Kanchi and A. Kanevsky, A note on approximating graph genus, Inform. Process Lett. 61 (1997) 317–322. doi:10.1016/S0020-0190(97)00203-2

[11] R.J. Cimikowski, On heuristics for determining the thickness of a graph, Inform. Sci. 85 (1995) 87–98. doi:10.1016/0020-0255(95)00011-D

[12] A.M. Dean, J.P. Hutchinson and E.R. Scheinerman, On the thickness and arboricity of a graph, J. Combin. Theory Ser. B 52 (1991) 147–151. doi:10.1016/0095-8956(91)90100-X

[13] R. Decker, H. Glover and J.P. Huneke, The genus of the 2 -amalgamations of graphs, J. Graph Theory 5 (1981) 95–102. doi:10.1002/jgt.3190050107

[14] J.H. Halton, On the thickness of graphs of given degree, Inform. Sci. 54 (1991) 219–238. doi:10.1016/0020-0255(91)90052-V

[15] A.M. Hobbs, A survey of thickness, in: Recent Progress in Combinatorics (Proc. 3rd Waterloo Conf. on Combinatorics, 1968), W.T. Tutte (Ed(s)), (New York, Academic Press, 1969) 255–264.

[16] M. Kleinert, Die Dicke des n-dimensionalen Würfel-Graphen, J. Combin. Theory 3 (1967) 10–15. doi:10.1016/S0021-9800(67)80010-3

[17] A. Mansfield, Determining the thickness of graphs is NP-hard, Math. Proc. Cambridge Philos. Soc. 93 (1983) 9–23. doi:10.1017/S030500410006028X

[18] E. Mäkinen and T. Poranen, An annotated bibliography on the thickness, outerthickness, and arboricity of a graph, Missouri J. Math. Sci. 24 (2012) 76–87.

[19] P. Mutzel, T. Odenthal and M. Scharbrodt, The thickness of graphs: a survey, Graphs Combin. 14 (1998) 59–73. doi:10.1007/PL00007219

[20] T. Poranen, A simulated annealing algorithm for determining the thickness of a graph, Inform. Sci. 172 (2005) 155–172. doi:10.1016/j.ins.2004.02.029

[21] W.T. Tutte, The thickness of a graph, Indag. Math. 25 (1963) 567–577. doi:10.1016/S1385-7258(63)50055-9

[22] J.M. Vasak, The thickness of the complete graph, Notices Amer. Math. Soc. 23 (1976) A–479.