Geodesic
On the Crossing Numbers of Cartesian Products of Wheels and Trees
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 2, pp. 399-413.

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

Bokal developed an innovative method for finding the crossing numbers of Cartesian product of two arbitrarily large graphs. In this article, the crossing number of the join product of stars and cycles are given. Afterwards, using Bokal’s zip product operation, the crossing numbers of the Cartesian products of the wheel Wn and all trees T with maximum degree at most five are established.
Keywords: graph, drawing, crossing number, join product, Cartesian product 
@article{DMGT_2017_37_2_a6,
     author = {Kle\v{s}\v{c}, Mari\'an and Petrillov\'a, Jana and Valo, Mat\'u\v{s}},
     title = {On the {Crossing} {Numbers} of {Cartesian} {Products} of {Wheels} and {Trees}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {399--413},
     publisher = {mathdoc},
     volume = {37},
     number = {2},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a6/}
}
TY  - JOUR
AU  - Klešč, Marián
AU  - Petrillová, Jana
AU  - Valo, Matúš
TI  - On the Crossing Numbers of Cartesian Products of Wheels and Trees
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 399
EP  - 413
VL  - 37
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a6/
LA  - en
ID  - DMGT_2017_37_2_a6
ER  - 
%0 Journal Article
%A Klešč, Marián
%A Petrillová, Jana
%A Valo, Matúš
%T On the Crossing Numbers of Cartesian Products of Wheels and Trees
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 399-413
%V 37
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a6/
%G en
%F DMGT_2017_37_2_a6
Klešč, Marián; Petrillová, Jana; Valo, Matúš. On the Crossing Numbers of Cartesian Products of Wheels and Trees. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 2, pp. 399-413. http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a6/

[1] D. Archdeacon and R.B. Richter, On the parity of crossing numbers, J. Graph Theory 12 (1988) 307-310. doi: 10.1002/jgt.3190120302

[2] K. Asano, The crossing number of K1,3,n and K2,3,n, J. Graph Theory 10 (1986) 1-8. doi: 10.1002/jgt.3190100102

[3] L.W. Beineke and R.D. Ringeisen, On the crossing numbers of products of cycles and graphs of order four, J. Graph Theory 4 (1980) 145-155. doi: 10.1002/jgt.3190040203

[4] D. Bokal, On the crossing numbers of Cartesian products with paths, J. Combin. Theory Ser. B 97 (2007) 381-384. doi: 10.1016/j.jctb.2006.06.003

[5] D. Bokal, On the crossing numbers of Cartesian products with trees, J. Graph Theory 56 (2007) 287-300. doi: 10.1002/jgt.20258

[6] C. Buchheim, M. Chimani, D. Ebner, C. Gutwenger, M. Jnger, G.W. Klau, P. Mutzel and R. Weiskircher, A branch-and-cut approach to the crossing number problem, Discrete Optimization 5 (2008) 373-388. doi: 10.1016/j.disopt.2007.05.006

[7] M. Chimani, P. Mutzel and I. Bomze, A new approach to exact crossing minimization, 16th Annual European Symposium on Algorithms 2008, Karlsruhe (ESA 08), Springer, Lecture Notes in Comput. Sci. 5193 (2008) 284-296. doi: 10.1007/978-3-540-87744-8 24

[8] M. Chimani, C. Gutwenger and P. Mutzel, Experiments on exact crossing minimization using column generation, ACM J. Exp. Algorithmics 14 (2009) 4.1-4.18.

[9] M. Chimani and T. Wiedera, An ILP-based proof system for the crossing number problem, 24th Annual European Symposium of Algorithms (ESA 2016), Aarhus, Denmark, Leibniz. Int. Proc. Inform. 57 (2016) 29.1-29.13. doi: 10.4230/LIPIcs.ESA.2016.29

[10] L.Y. Glebsky and G. Salazar, The crossing number of Cm × Cn is as conjectured for n ≥ m(m + 1), J. Graph Treory 47 (2004) 53-72. doi: 10.1002/jgt.20016

[11] F. Harary, P.C. Kainen and A.J. Schwenk, Toroidal graphs with arbitrarily high crossing numbers, Nanta Math. 6 (1973) 58-67.

[12] Y. Huang and T. Zhao, The crossing number of K1,4,n, Discrete Math. 308 (2008) 1634-1638. doi: 10.1016/j.disc.2006.12.002

[13] H. Mei and Y. Huang, The crossing number of K1,5,n, Internat. J. Math. Combin. 1 (2007) 33-44.

[14] S. Jendrol’ and M. Ščerbová, On the crossing numbers of Sm × Pn and Sm × Cn, Čas. Pestování Mat. 107 (1982) 225-230.

[15] M. Klešč, The crossing numbers of products of paths and stars with 4-vertex graphs, J. Graph Theory 18 (1994) 605-614. doi: 10.1002/jgt.3190180608

[16] M. Klešč, The crossing numbers of Cartesian products of paths with 5-vertex graphs, Discrete Math. 233 (2001) 353-359. doi: 10.1016/S0012-365X(00)00251-X

[17] M. Klešč, The join of graphs and crossing numbers, Electron. Notes Discrete Math. 28 (2007) 349-355. doi: 10.1016/j.endm.2007.01.049

[18] M. Klešč, The crossing numbers of join of the special graph on six vertices with path and cycle, Discrete Mat. 310 (2010) 1475-1481. doi: 10.1016/j.disc.2009.08.018

[19] M. Klešč and D. Kravecová, The crossing numbers of P2n□C3, Discrete Mat. 312 (2012) 2096-2101. doi: 10.1016/j.disc.2011.03.028

[20] M. Klešč and J. Petrillová, On the optimal drawings of products of paths with graphs, Acta Electrotechnica et Informatica 13 (2013) 56-61. doi: 10.2478/aeei-2013-0041

[21] M. Klešč and Š. Schrötter, The crossing numbers of join products of paths with graphs of order four, Discuss. Math. Graph Theory 31 (2011) 312-331. doi: 10.7151/dmgt.1548

[22] M. Klešč and Š. Schrötter, The crossing numbers of join of paths and cycles with two graphs of order five, Mathematical Modeling and Computational Science, Springer, Lecture Notes in Comput. Sci. 7125 (2012) 160-167. doi: 10.1007/978-3-642-28212-6 15

[23] M. Klešč and M. Valo, Minimum crossings in join of graphs with paths and cycles, Acta Electrotechnica et Informatica 12 (2012) 32-37. doi: 10.2478/v10198-012-0028-0

[24] D.J. Kleitman, The crossing number of K5,n, J. Combin. Theory Ser. B 9 (1971) 315-323. doi: 10.1016/S0021-9800(70)80087-4

[25] D. Kravecová and J. Petrillová, The crossing number of P2n□C4, Acta Electrotechnica et Informatica 12 (2012) 42-46. doi: 10.2478/v10198-012-0030-6

[26] Z. Ouyang, W. Jing and Y. Huang, On the crossing numbers of the Cartesian product path with complete graph, Discrete Math. 328 (2014) 71-78. doi: 10.1016/j.disc.2014.03.011

[27] W. Zheng, X. Lin, Y. Yang and C. Deng, On the crossing numbers of Km□Cn and Km,l□Pn, Discrete Appl. Math. 156 (2008) 1899-1907. doi: 10.1016/j.dam.2007.09.007