图的交叉数问题研究
|
摘要
图的交叉数问题是在实际应用中提出来的，在电子线路板的设计，CAD领域有广阔的应用。目前已经确定交叉数的图类主要集中于顶点数较小或者交叉数较小的图。本文对一些顶点数较大或交叉数较大的图的交叉数问题进行研究，将计算机构造性证明和数学证明相结合，取得了较好的结果。
本课题组给出的交叉数算法CCN已被成功地用于计算顶点数较小的图的交叉数。但由于图的交叉数问题是NP困难问题，对顶点数较大或交叉数较大的图，所需要的计算时间仍然太多。针对这一问题，本文给出了计算图的交叉数上界的算法CCN~*，把计算图的交叉数上界问题转化为计算往其子图的较少交叉点画法中回添边时所产生的交叉数的问题，从而可以对较大规模的图的交叉数性质进行研究。利用该算法计算了顶点数p≤12的所有路径幂图P_n~k和13≤p≤20且k≤9的所有P_n~k的较好的交叉数上界。
对与圈C_n交图的交叉数，目前研究的较多的是两个圈的交图以及顶点数较小的图与圈交图的交叉数。Ringeisen和Beineke对K_m□C_n，m≤4进行了研究。本文对K_m□C_n进行研究，给出了相应的交叉数计数方法，确定了这类图的交叉数下界。对m=5，6，7或者n为不小于4的偶数，给出了交叉数上界及对应的画法；如果著名的完全图交叉数猜想对K_(m+2)成立，则本文给出的交叉数上界就是完全图K_m与圈C_n交图的交叉数。
对与路径P_n交图的交叉数，目前研究的较多的也是顶点数较小的图与路径交图的交叉数。Kle(?)等人对K_m□P_n，m≤5进行了研究。Bokal对K_(1，l)□P_n进行了研究。黄元秋与Kle(?)分别研究了W_m□P_n的n≤3与m=3，4的情形；Kle(?)对W_(2，3)□P_n进行了研究。本文针对K_m□P_n，K_(m，l)□P_n，W_(l，m)□P_n进行了研究，给出了这些图的交叉数上界。并对其中K_m□P_n，K_(2，l)□P_n，W_m□P_n，W_(2，m)□P_n给出了相应的交叉数计数方法，进而导出了这些图的交叉数下界。并最终确定了K_6□P_n，K_(2，l)□P_n，W_m□P_n，W_(2，m)□P_n的交叉数，扩展了与路径交图的交叉数的研究结果。
本文所给出的交叉数研究方法还可以用于研究其它图的交叉数问题。作为应用实例，本文确定了两类三正则图Kn(?)del图J_(3，n)和Flower Snark及其相关图F_n的交叉数。相信该方法在图的交叉数问题研究中还有更广泛的应用。
Crossing numbers of graphs are in general very difficult to compute. The exact crossing numbers of very few families of graphs are known. Using computer algorithm to compute upper bounds, and using mathmatical techniques to get lower bounds, this thesis researches on the crossing numbers of some graphs with relative large order or with relative large crossing number.
The exist algorithm CCN proposed in 2002 computes the crossing numbers of all the graphs with some order. Unfortunately, the crossing number of a graph is NP complete, and not much hope is held for efficiently finding all optimal drawings-or even a single optimal drawing-for all graphs. An algorithm CCN~* is presented in the thesis to compute upper bounds of the crossing number of path power graphs P_n~k. Let p=|V(G)|. The upper bounds of crossing numbers of P_n~k where p≤12 or 13≤p≤20 with k≤9 are computed by CCN~*.
Then we investigate the Crossing number of Cartesian products with cycles and paths. For the Cartesian product of cycle and complete graph, Ringeisen and Beineke have proved that cr(C_3□C_n)=n and cr(K_4□C_n)=3n. The thesis obtains a lower bound for K_m□C_n using a special crossing counting method for K_m□C_n, i.e. cr(K_m□C_n)≥n×cr(K_(m+2)) for n≥3 and m≥5. It is also proved that, cr(K_m□C_n)≤n/4(?)(m+2)/2」(?)(m+1)/2」(?)m/2」(?)(m-1)/2」for m=5, 6, 7 and for m≥5 with even n≥4, and the equality holds for m=5, 6, 7 and for m=8, 9, 10 with even n≥4.
The thesis also studies the Cartesian product of path with complete graph K_m, complete bipartite graph K_(m,l) and cone, respectively. A special crossing counting method for the Cartesian product with paths is presented to obtain lower bounds of cr(K_m□P_n), cr(K_(2,l)□P_n), cr(W_m□P_n) and cr(W_(2.m)□P_n). And the crossing number of K_6□P_n, K_(2,1)□P_n, W_m□P_n and W_(2,m)□P_n are determined.
Finally, we use the counting methods developed in this thesis to study other crossing number problems. As application examples, the crossing numbers of Kn(?)del graph J_(3,n) and Flower Snark and related graph F_n are determined.
本课题组给出的交叉数算法CCN已被成功地用于计算顶点数较小的图的交叉数。但由于图的交叉数问题是NP困难问题，对顶点数较大或交叉数较大的图，所需要的计算时间仍然太多。针对这一问题，本文给出了计算图的交叉数上界的算法CCN~*，把计算图的交叉数上界问题转化为计算往其子图的较少交叉点画法中回添边时所产生的交叉数的问题，从而可以对较大规模的图的交叉数性质进行研究。利用该算法计算了顶点数p≤12的所有路径幂图P_n~k和13≤p≤20且k≤9的所有P_n~k的较好的交叉数上界。
对与圈C_n交图的交叉数，目前研究的较多的是两个圈的交图以及顶点数较小的图与圈交图的交叉数。Ringeisen和Beineke对K_m□C_n，m≤4进行了研究。本文对K_m□C_n进行研究，给出了相应的交叉数计数方法，确定了这类图的交叉数下界。对m=5，6，7或者n为不小于4的偶数，给出了交叉数上界及对应的画法；如果著名的完全图交叉数猜想对K_(m+2)成立，则本文给出的交叉数上界就是完全图K_m与圈C_n交图的交叉数。
对与路径P_n交图的交叉数，目前研究的较多的也是顶点数较小的图与路径交图的交叉数。Kle(?)等人对K_m□P_n，m≤5进行了研究。Bokal对K_(1，l)□P_n进行了研究。黄元秋与Kle(?)分别研究了W_m□P_n的n≤3与m=3，4的情形；Kle(?)对W_(2，3)□P_n进行了研究。本文针对K_m□P_n，K_(m，l)□P_n，W_(l，m)□P_n进行了研究，给出了这些图的交叉数上界。并对其中K_m□P_n，K_(2，l)□P_n，W_m□P_n，W_(2，m)□P_n给出了相应的交叉数计数方法，进而导出了这些图的交叉数下界。并最终确定了K_6□P_n，K_(2，l)□P_n，W_m□P_n，W_(2，m)□P_n的交叉数，扩展了与路径交图的交叉数的研究结果。
本文所给出的交叉数研究方法还可以用于研究其它图的交叉数问题。作为应用实例，本文确定了两类三正则图Kn(?)del图J_(3，n)和Flower Snark及其相关图F_n的交叉数。相信该方法在图的交叉数问题研究中还有更广泛的应用。
Crossing numbers of graphs are in general very difficult to compute. The exact crossing numbers of very few families of graphs are known. Using computer algorithm to compute upper bounds, and using mathmatical techniques to get lower bounds, this thesis researches on the crossing numbers of some graphs with relative large order or with relative large crossing number.
The exist algorithm CCN proposed in 2002 computes the crossing numbers of all the graphs with some order. Unfortunately, the crossing number of a graph is NP complete, and not much hope is held for efficiently finding all optimal drawings-or even a single optimal drawing-for all graphs. An algorithm CCN~* is presented in the thesis to compute upper bounds of the crossing number of path power graphs P_n~k. Let p=|V(G)|. The upper bounds of crossing numbers of P_n~k where p≤12 or 13≤p≤20 with k≤9 are computed by CCN~*.
Then we investigate the Crossing number of Cartesian products with cycles and paths. For the Cartesian product of cycle and complete graph, Ringeisen and Beineke have proved that cr(C_3□C_n)=n and cr(K_4□C_n)=3n. The thesis obtains a lower bound for K_m□C_n using a special crossing counting method for K_m□C_n, i.e. cr(K_m□C_n)≥n×cr(K_(m+2)) for n≥3 and m≥5. It is also proved that, cr(K_m□C_n)≤n/4(?)(m+2)/2」(?)(m+1)/2」(?)m/2」(?)(m-1)/2」for m=5, 6, 7 and for m≥5 with even n≥4, and the equality holds for m=5, 6, 7 and for m=8, 9, 10 with even n≥4.
The thesis also studies the Cartesian product of path with complete graph K_m, complete bipartite graph K_(m,l) and cone, respectively. A special crossing counting method for the Cartesian product with paths is presented to obtain lower bounds of cr(K_m□P_n), cr(K_(2,l)□P_n), cr(W_m□P_n) and cr(W_(2.m)□P_n). And the crossing number of K_6□P_n, K_(2,1)□P_n, W_m□P_n and W_(2,m)□P_n are determined.
Finally, we use the counting methods developed in this thesis to study other crossing number problems. As application examples, the crossing numbers of Kn(?)del graph J_(3,n) and Flower Snark and related graph F_n are determined.
引文
[1] Székely L A. A successful concept for measuring non-planarity of graphs: the crossing number. Discrete Mathematics, 2004, 276:331-352.
[2] Pach J, Tth G. Which crossing number is it anyway? Journal of Combinatorial Theory, Series B, 2000, 80:225-246.
[3] Pelsmajer M J, Schaefer M, tefankovic. Odd crossing number is not crossing number, 2006, 3843:386-396.
[4] Zarankiewicz K. On a problem of P. Turàn concerning graphs. Fund Math, 1954, 41:137-145.
[5] Guy R K. The decline and fall of Zarankiewicz's theorem. Proof Techniques in Graph Theory. New York: Academic Press, 1969:63-69.
[6] Garey M R, Johnson D S. Crossing number is NP-complete. SIAM J. Alg. Disc. Meth., 1983, 4(3):312-316.
[7] Hliněn P. Crossing number is hard for cubic graphs. Journal of Combinatorial Theory, B, 2006, 96:455-471.
[8] Harary E Graph Theory. Boston: Addison-Wesley Publishing Company, 1972.
[9] Bondy J A, Murty U S R. Graph Theory with Applications. North Holland, New York: The Macmillan Press, 1976.
[10] 徐俊明．图论及其应用．合肥：中国科学技术大学出版社，1998．
[11] Chlebus B S, Gasieniec L, Kowalski D R. Bounding work and communication in robust cooperative computation. Lecture Notes in Computer Science, 2002:295-310.
[12] Sun F, Yang Y S, Han S. Harmony of graphs C_(2j+l)U C_(2k) and graphs P_n~k. Journal of Dalian University of Technology, 2000, 40(4):384-387.
[13] Kndel W. New gossips and telephones. Discrete Math., 1975, 13:95.
[14] Fraigniaud E Peters J G. Minimum linear Gossip graphs and maximal linear (A, k)-Gossip gaphs. Networks, 2001, 38(3):150-162.
[15] Cohen J, Fraigniaud R Gavoille C. Recognizing Kndel graphs. Discrete Mathematics, 2002, 250:41-62.
[16] Fertin G, Raspaud A. A survey on Kndel graphs. Discrete Applied Mathematics, 2004, 137:173-195.
[17] Cavicchioli A., Murgolo T E, Ruini B. Special classes of snarks. Acta Applicandae Mathematicae, 2003, 76:57-88.
[18] Cavicchioli A., Meschiari M, Ruini B. A survey on snarks and new results: products, reducibility and a computer search. Journal of Graph Theory, 1998, 28:57-86.
[19] Steffen E. Classifications and characterizations of snarks. Discrete Mathematics, 1998, 188:183-203.
[20] Isaacs R. Infinite families of nontrivial trivalent graphs which are not Tait colorable. Amer. Math. Monthly, 1975, 82:221 - 239.
[21] Fiorini S. On the crossing number of generalized Petersen graphs. Ann. Discrete Math, 1986, 30:221-242.
[22] Archdeacon D. Problems in topological graph theory, http://www.cem.uvm.edu/ archdeac/problems/problems.html, 1995.
[23] Grohe M. Computing crossing numbers in quadratic time. Journal of Computer and System Sciences, 2004, 68:285 - 302.
[24] Ajtai M, Chvatal V, Newborn M, Szemeredi E. Crossing-free subgraphs. Annuals of Discrete Mathematics, 1982, 12:9-12.
[25] Leighton T. Complexity Issues in VLSI, Foundations of Computing Series. Cambridge: MIT Press, 1983.
[26] Pach J, Radoicic R, Tardos G, Toth G. Improving the crossing lemma by finding more crossings in sparse graphs. Discrete Comput. Geom., 2006, 36:527-552.
[27] Guy R K. A combinatorial problem. Nabla(Bull. Malayan Math. Soc.), 1960, 7:68-72.
[28] Guy R K. Crossing number of graphs. Lecture Notes in Mathematics, 1972, 303:111-124.
[29] Archdeacon D. Topological graph: a survey. Cong, numerantium, 1996, 115:5-54.
[30] Blazek J, Koman N. A minimal problem concerning complete plane graphs, in: Proceedings of the Symposium on Smolenice, ed., Fiedler, Theory of Graphs and its Applications. Prague: Publ. House of the Czechoslovak Academy of Sciences, 1963:113-117.
[31] Tutte W T. Toward a theory of crossing numbers. J. Combinatorial Theory, 1970, 8:45-53.
[32] Erdos P, Guy R K. Crossing number problems. Amer. Math. Monthly, 1973, 88:52-58.
[33] Brodsky A, Durocher S. The rectilinear crossing number of K_(10) is 62. The Electronic Journal of Combinatorics, 2001, 23(8): 1-30.
[34] Aichholzer O, Aurenhammer F, Krasser H. Enumerating order types for small point sets with applications. Order, 2002:265-281.
[35] Aichholzer O, Aurenhammer F, Krasser H. On the crossing number of complete graphs. Computing, 2006:165-176.
[36] Turàn E A note of welcome. J. Graph Theory, 1977, 1:7-9.
[37] Kleitman D J. The crossing number of K_(5.n).J. Combin. Theory, 1970, 9:315-323.
[38] Woodall D R. Cyclic-order graphs and Zarankiewicz's crossing-number conjecture. J. Graph Theory, 1993, 17:657-671.
[39] Nahas N H. On the crossing number of K_(m,n). The Electronic Journal of Combinatorics, 2003, 10(8):1-6.
[40] Klerk E D, Maharry J, Pasechnik D V, Richiter R B, Salazar G. Improved bounds for the crossing numbers of K_(m,n) and K_n. SIAM J. DISCRETE MATH., 2006, 20(1): 189-202.
[41] Asano K. The crossing number of K_(1,3,n) and K_(2,3.n). Journal of Graph Theory, 1986, 10:1-8.
[42] Huang Y Q, Zhao T L. The crossing number of K_(1,4.n). Discrete Mathematics, 2007, doi: 10.1016/j .disc.2006.12.002.
[43] 黄元秋，赵霆雷．On the crossing number of the complete tripartite graph K_(1,8.n)．数学物理学报，2006，7：1115-1122．
[44] 黄元秋，赵霆雷．关于完全3-部图K_(1，6，n)的交叉数．应用数学学报，2006，29(6)：1046-1053．
[45] 赵霆雷．线图与若干典型图类的交叉数研究：(博士学位论文)．长沙：湖南师范大学，2006．
[46] Exoo G, Harary F, Kabe11 J. The crossing numbers of some generalized Petersen graphs. Math. Scand., 1981, 48:184-188.
[47] 马登举，任韩，卢俊杰．广义petersen图G(2m＋1，m)的交叉数．华东师范大学学报(自然科学版)，2005，1：34-39．
[48] Mcquillan D. On the crossing numbers of certain generalized Petersen graphs. Ann. Discrete Math., 1992, 104:311-320.
[49] Richter R B, Salazar G. The crossing number P(N; 3). Graphs and Combinatorics, 2002, 18:381-394.
[50] Chia G L, Lee C L. Crossing numbers and skewness of some generalized Petersen graphs. Lecture Notes in Computer Science, 2005, 3330:80-86.
[51] Fiorini S, Gauci J B. The crossing number of the generalized Petersen graph P(3k, k). Mathematica Bohemica, 2003, 128:337-347.
[52] Salazar G. On the crossing numbers of loop networks and generalized Petersen graphs. Discrete Mathematics, 2005, 302:243-253.
[53] 马登举，任韩，卢俊杰．循环图交叉数的新结果．南华大学学报(理工版)，2003，17(4)：17-20．
[54] 卢俊杰，吴雅容，任韩．Crossing number of certain circular graphs．华东师范大学学报(自然科学版)，2005，2：16-21,26．
[55] Liu T Y, Liu Y R On the crossing number of circular graphs. OR Transactions, 1998, 2(4):31-38.
[56] Hao R X, Liu Y E New upper bounds on crossing number of circular graphs. OR Transactions, 1999, 3(2): 1-6.
[57] 郝荣霞，刘彦佩．利用辅助图计算交叉数．河南师范大学学报(自然科学版)，2002，2：7-13．
[58] 杨元生，赵承业．循环图C_n(1，k)的交叉数．中国计算机学会2001年全国软件技术研讨会论文集．大连：大连出版社，2001：134-136．
[59] Yang Y S, Lin X H, Lü J G. The crossing number of C(n; {1, 3}). Discrete Mathematics, 2004, 289:107-118.
[60] Lin X H, Yang Y S, Lü J G. The crossing number of C(mk; {1, k}). Graphs and Combinatorics, 2005, 21:89-96.
[61] Lin X H, Yang Y S, Lü J G. The crossing number of C(n; {1, n/2 - 1}). Utilas Math. to appear.
[62] Ma D J, Ren It, Lu J J. The crossing numbers of the circular graph C(2m＋2, m). Discrete Math., 2005, 1304:88-93.
[63] Ho P T. The crossing number of C(3k＋1; {1, k}). Discrete Mathematics. To appear.
[64] Harary F, Kainen P C, Schwenk J. Toroidal graphs with arbitrarily high crossing numbers. Nanta Math., 1973, 6:58-67.
[65] Ringeisen R D, Beineke L W. The crossing number of C_3× Cn. J. Combin. Theory, 1978, 24:134-136.
[66] Beineke L W, Ringeisen R D. On the crossing numbers of products of cycles and graphs of order four. J. Graph Theory, 1980,4:145-155.
[67] Eggleton R B, Guy R K. The crossing number of the n-cube. Notices Amer. Math. Soc, 1970,17:757.
[68] Dean A M, Rithcter R B. The crossing number of C_4×C_4. Journal of Graph Theory, 1995, 19:125-129.
[69] Richter R B, Thomassen C. Intersections of curve systems and the crossing number of C_5×C_5. Discrete Comput. Geom., 1995, 13:149-159.
[70] Klesc M, Richter R B, Stobert I. The crossing numbers of C_5×C_n. J. Graph Theory, 1996, 22(3):239-243.
[71] Anderson M, Richter R B, Rodney P. The crossing number of C_6×C_6. Cong. Numeran-tium, 1996, 118:97-107.
[72] Anderson M, Richter R B, Rodney P. The crossing number of C_7×C_7. Cong. Numeran-tium, 1997, 125:97-117.
[73] Richter R B, Salazar G. The crossing number of C_6×C_n. Australasian Journal of Combinatorics, 2001, 23:135-144.
[74] Adamsson J. The theory of arrangement: (Ph.D. Dissertation). Ottawa,: Carleton University, 2000.
[75] Shahrokhi F, Sykora O, Szekely L A, Vrt'o I. Intersection of curves and crossing number of C_m×C_n on surfaces. Discrete Comput. Geom., 1998,19:237-247.
[76] Salazar G. On the intersections of systems of curves. Journal of Combinatorial Theory, Series B, 1999, 75:56-60.
[77] Salazar G. Drawing of C_m×C_n with one disjoint family. Journal of Combinatorial Theory, Series B, 1999,76:129-135.
[78] Salazar G. Crossing numbers of certain families of graphs: (Ph.D. Dissertation). Ottawa,: Carleton University, 1997.
[79] Juarez H A, Salazar G. Drawings of C_m×C_n with one disjoint family ii. Journal of Combinatorial Theory, Series B, 2001, 82:161-165.
[80] Adamsson J, Richter R B. Arrangements, circular arrangements and the crossing number of C_7×C_n. J. Combin. Theory, Series B, 2004, 90:21-39.
[81] Salazar G, Ugalde E. An improved bound for the crossing number of C_m×C_n: a self-contained proof using mostly combinatorial arguments. Graphs and Combinatorics, 2004, 20:247-.253.
[82] Glebsky L Y, Salazar G. The crossing number of Cm×C,, is as conjectured for n≥ m(m＋1). J. Graph Theory, 2004, 47:53-72.
[83] Jendro S, erbovà M. On the crossing numbers of S_m×P_n and S_m×C_n. asopis pro pěstovàn matematiky, 1982, 107:225-230.
[84] Kle M. On the crossing numbers of Cartesian products of paths and stars or cycles. Math. Slovaca, 1991, 41:113-120.
[85] Kle M. The crossing numbers of 5-vertex graphs with paths and cycles. Discuss. Math. Graph Theory., 1999, 19:59-69.
[86] Kle M, Richter R B, Stobert I. The crossing numbers of K_(2.3)×C_n. Discrete Mathematics, 2002, 251:109-117.
[87] Kle M, Kocǘovà A. The crossing numbers of products of 5-vertex graphs with cycles. Discrete Mathematics, 2007, 307:1395-1403.
[88] Kle M. The crossing numbers of products of paths and stars with 4-vertex graphs. J. Graph Theory., 1994, 6:605-614.
[89] Kle M. The crossing numbers of K_(2,3)×P_n and K_(2,3)×S_n. Tatra Mountains Math. Publ., 1996, 9:51-56.
[90] Kle M. The crossing numbers of K_5×P_n. Tatra Mt. Math. Publ., 1999, 18:63-68.
[91] Kle M. The crossing numbers of Cartesian products of paths with 5-vertex graphs. Discrete Mathematics, 2001, 233:353-359.
[92] 肖文兵，黄元秋．一类迪卡积图的交叉数．湖南师范大学自然科学版，2003，26(4)：3-7，17．
[93] 何小年，黄元秋．一类迪卡尔积交叉数．吉首大学学报(自然科学版)，2005，26(1)：8-11．
[94] Wang J, Huang Y Q. The crossing numbers of Cartesian products of paths with 6-vertex graphs. Journal of Jishou University(Natural Science Edition), 2005, 26(2):9-13.
[95] Peng Y H, Yiew Y C. The crossing number of P(3, 1)×p_n. Discrete Mathematics. DOI: 10.1016/j .disc .2006.03.058.
[96] 周智勇，黄元秋．笛卡尔积图K_3，3P_n的交叉数．湖南师范大学自然科学学报，2007，30(1)：31-34．
[97] Huang Y Q, YU R On the crossing numbers of P_m×W_n. Journal of Natural Science of Hunan Normal University, 2005, 28:14-16.
[98] Bokal D, Beineke L W. On the crossing number of Cartesian products with paths. J. Combinatorial Theory, Series B, 2007, 97:381-384.
[99] Kle M. On the crossing numbers of products of stars and graphs of order five. Graphs and Combinatorics, 2001, 17:289-294.
[100] Kle M. The join of graphs and crossing numbers. Electronic Notes in Discrete Mathematics, 2007, 28:349-355.
[101] Kulli V R, Akka D G, Beineke L W. On the line graphs with crossing number 1. J. Graph Theory, 1979, 3:87-90.
[102] Jendro S, Kle M. On the graphs whose line graphs have crossing number one. J. Graph Theory, 2001, 37:181-188.
[103] Akka D G, Jendro S, Kle M, Panshetty S V. On the line graphs with crossing number 1. Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat., 1997, 8:3-8.
[104] Kochol M. Construction of crossing-critical graphs. Discrete Math., 1987, 66:311-313.
[105] Geelen J F, Richter R B, Salazar G. Embedding grids in surfaces. European Journal of Combinatorics, 2004, 25:785-792.
[106] Hlinn P. Crossing-critical graphs have bounded path-width. Journal of Combinatorial Theory, B, 2003, 88:347-367.
[107] Huang J, Xu J M. The bondage numbers of graphs with small crossing numbers. Discrete Mathematics. DOI: 10.1016/j.disc.2006.09.035, 2006.
[108] Garey M R, Johnson D S. The NP-completeness column: An ongoing guide. Journal of Algorithms, 1982, 3:89-99.
[109] Hopcroft J E, Tarjan R. Efficient planarity testing. Journal of ACM, 1974, 21:549-568.
[110] Haris F C, Harris C R. A proposed algorithm for calculating the minimum crossing number of a graph, in: Proc. 8th. Quadrennial Intl. Conference on Graph Theory, Combinatorics, Algorithms and Applications. 1996.
[111] 杨元生，王丹，陆维明．四正则图的交叉数．软件学报，2002，13(12)：2259-2266．
[112] 林晓惠．图的交叉数等图论难题的研究：(博士学位论文)．大连：大连理工大学，2004．
[113] 杨元生，孙艳春，陆维明．不超过9个顶点的所有图的交叉数．小型微型计算机系统，2003，24(6)：954-958．
[114] Guy R K. Latest results on crossing nubmers. Recent Trends in Graph Theory, 1971, 1:143-156.
[115] Beineke L W, Wilson R. Selected topics in graph theory. USA: Academic Press, 1978.
[116] Archdeacon D, Richter R B. On the parity of crossing nubmers. J. Graph Theory, 1988, 12:307-310.
[2] Pach J, Tth G. Which crossing number is it anyway? Journal of Combinatorial Theory, Series B, 2000, 80:225-246.
[3] Pelsmajer M J, Schaefer M, tefankovic. Odd crossing number is not crossing number, 2006, 3843:386-396.
[4] Zarankiewicz K. On a problem of P. Turàn concerning graphs. Fund Math, 1954, 41:137-145.
[5] Guy R K. The decline and fall of Zarankiewicz's theorem. Proof Techniques in Graph Theory. New York: Academic Press, 1969:63-69.
[6] Garey M R, Johnson D S. Crossing number is NP-complete. SIAM J. Alg. Disc. Meth., 1983, 4(3):312-316.
[7] Hliněn P. Crossing number is hard for cubic graphs. Journal of Combinatorial Theory, B, 2006, 96:455-471.
[8] Harary E Graph Theory. Boston: Addison-Wesley Publishing Company, 1972.
[9] Bondy J A, Murty U S R. Graph Theory with Applications. North Holland, New York: The Macmillan Press, 1976.
[10] 徐俊明．图论及其应用．合肥：中国科学技术大学出版社，1998．
[11] Chlebus B S, Gasieniec L, Kowalski D R. Bounding work and communication in robust cooperative computation. Lecture Notes in Computer Science, 2002:295-310.
[12] Sun F, Yang Y S, Han S. Harmony of graphs C_(2j+l)U C_(2k) and graphs P_n~k. Journal of Dalian University of Technology, 2000, 40(4):384-387.
[13] Kndel W. New gossips and telephones. Discrete Math., 1975, 13:95.
[14] Fraigniaud E Peters J G. Minimum linear Gossip graphs and maximal linear (A, k)-Gossip gaphs. Networks, 2001, 38(3):150-162.
[15] Cohen J, Fraigniaud R Gavoille C. Recognizing Kndel graphs. Discrete Mathematics, 2002, 250:41-62.
[16] Fertin G, Raspaud A. A survey on Kndel graphs. Discrete Applied Mathematics, 2004, 137:173-195.
[17] Cavicchioli A., Murgolo T E, Ruini B. Special classes of snarks. Acta Applicandae Mathematicae, 2003, 76:57-88.
[18] Cavicchioli A., Meschiari M, Ruini B. A survey on snarks and new results: products, reducibility and a computer search. Journal of Graph Theory, 1998, 28:57-86.
[19] Steffen E. Classifications and characterizations of snarks. Discrete Mathematics, 1998, 188:183-203.
[20] Isaacs R. Infinite families of nontrivial trivalent graphs which are not Tait colorable. Amer. Math. Monthly, 1975, 82:221 - 239.
[21] Fiorini S. On the crossing number of generalized Petersen graphs. Ann. Discrete Math, 1986, 30:221-242.
[22] Archdeacon D. Problems in topological graph theory, http://www.cem.uvm.edu/ archdeac/problems/problems.html, 1995.
[23] Grohe M. Computing crossing numbers in quadratic time. Journal of Computer and System Sciences, 2004, 68:285 - 302.
[24] Ajtai M, Chvatal V, Newborn M, Szemeredi E. Crossing-free subgraphs. Annuals of Discrete Mathematics, 1982, 12:9-12.
[25] Leighton T. Complexity Issues in VLSI, Foundations of Computing Series. Cambridge: MIT Press, 1983.
[26] Pach J, Radoicic R, Tardos G, Toth G. Improving the crossing lemma by finding more crossings in sparse graphs. Discrete Comput. Geom., 2006, 36:527-552.
[27] Guy R K. A combinatorial problem. Nabla(Bull. Malayan Math. Soc.), 1960, 7:68-72.
[28] Guy R K. Crossing number of graphs. Lecture Notes in Mathematics, 1972, 303:111-124.
[29] Archdeacon D. Topological graph: a survey. Cong, numerantium, 1996, 115:5-54.
[30] Blazek J, Koman N. A minimal problem concerning complete plane graphs, in: Proceedings of the Symposium on Smolenice, ed., Fiedler, Theory of Graphs and its Applications. Prague: Publ. House of the Czechoslovak Academy of Sciences, 1963:113-117.
[31] Tutte W T. Toward a theory of crossing numbers. J. Combinatorial Theory, 1970, 8:45-53.
[32] Erdos P, Guy R K. Crossing number problems. Amer. Math. Monthly, 1973, 88:52-58.
[33] Brodsky A, Durocher S. The rectilinear crossing number of K_(10) is 62. The Electronic Journal of Combinatorics, 2001, 23(8): 1-30.
[34] Aichholzer O, Aurenhammer F, Krasser H. Enumerating order types for small point sets with applications. Order, 2002:265-281.
[35] Aichholzer O, Aurenhammer F, Krasser H. On the crossing number of complete graphs. Computing, 2006:165-176.
[36] Turàn E A note of welcome. J. Graph Theory, 1977, 1:7-9.
[37] Kleitman D J. The crossing number of K_(5.n).J. Combin. Theory, 1970, 9:315-323.
[38] Woodall D R. Cyclic-order graphs and Zarankiewicz's crossing-number conjecture. J. Graph Theory, 1993, 17:657-671.
[39] Nahas N H. On the crossing number of K_(m,n). The Electronic Journal of Combinatorics, 2003, 10(8):1-6.
[40] Klerk E D, Maharry J, Pasechnik D V, Richiter R B, Salazar G. Improved bounds for the crossing numbers of K_(m,n) and K_n. SIAM J. DISCRETE MATH., 2006, 20(1): 189-202.
[41] Asano K. The crossing number of K_(1,3,n) and K_(2,3.n). Journal of Graph Theory, 1986, 10:1-8.
[42] Huang Y Q, Zhao T L. The crossing number of K_(1,4.n). Discrete Mathematics, 2007, doi: 10.1016/j .disc.2006.12.002.
[43] 黄元秋，赵霆雷．On the crossing number of the complete tripartite graph K_(1,8.n)．数学物理学报，2006，7：1115-1122．
[44] 黄元秋，赵霆雷．关于完全3-部图K_(1，6，n)的交叉数．应用数学学报，2006，29(6)：1046-1053．
[45] 赵霆雷．线图与若干典型图类的交叉数研究：(博士学位论文)．长沙：湖南师范大学，2006．
[46] Exoo G, Harary F, Kabe11 J. The crossing numbers of some generalized Petersen graphs. Math. Scand., 1981, 48:184-188.
[47] 马登举，任韩，卢俊杰．广义petersen图G(2m＋1，m)的交叉数．华东师范大学学报(自然科学版)，2005，1：34-39．
[48] Mcquillan D. On the crossing numbers of certain generalized Petersen graphs. Ann. Discrete Math., 1992, 104:311-320.
[49] Richter R B, Salazar G. The crossing number P(N; 3). Graphs and Combinatorics, 2002, 18:381-394.
[50] Chia G L, Lee C L. Crossing numbers and skewness of some generalized Petersen graphs. Lecture Notes in Computer Science, 2005, 3330:80-86.
[51] Fiorini S, Gauci J B. The crossing number of the generalized Petersen graph P(3k, k). Mathematica Bohemica, 2003, 128:337-347.
[52] Salazar G. On the crossing numbers of loop networks and generalized Petersen graphs. Discrete Mathematics, 2005, 302:243-253.
[53] 马登举，任韩，卢俊杰．循环图交叉数的新结果．南华大学学报(理工版)，2003，17(4)：17-20．
[54] 卢俊杰，吴雅容，任韩．Crossing number of certain circular graphs．华东师范大学学报(自然科学版)，2005，2：16-21,26．
[55] Liu T Y, Liu Y R On the crossing number of circular graphs. OR Transactions, 1998, 2(4):31-38.
[56] Hao R X, Liu Y E New upper bounds on crossing number of circular graphs. OR Transactions, 1999, 3(2): 1-6.
[57] 郝荣霞，刘彦佩．利用辅助图计算交叉数．河南师范大学学报(自然科学版)，2002，2：7-13．
[58] 杨元生，赵承业．循环图C_n(1，k)的交叉数．中国计算机学会2001年全国软件技术研讨会论文集．大连：大连出版社，2001：134-136．
[59] Yang Y S, Lin X H, Lü J G. The crossing number of C(n; {1, 3}). Discrete Mathematics, 2004, 289:107-118.
[60] Lin X H, Yang Y S, Lü J G. The crossing number of C(mk; {1, k}). Graphs and Combinatorics, 2005, 21:89-96.
[61] Lin X H, Yang Y S, Lü J G. The crossing number of C(n; {1, n/2 - 1}). Utilas Math. to appear.
[62] Ma D J, Ren It, Lu J J. The crossing numbers of the circular graph C(2m＋2, m). Discrete Math., 2005, 1304:88-93.
[63] Ho P T. The crossing number of C(3k＋1; {1, k}). Discrete Mathematics. To appear.
[64] Harary F, Kainen P C, Schwenk J. Toroidal graphs with arbitrarily high crossing numbers. Nanta Math., 1973, 6:58-67.
[65] Ringeisen R D, Beineke L W. The crossing number of C_3× Cn. J. Combin. Theory, 1978, 24:134-136.
[66] Beineke L W, Ringeisen R D. On the crossing numbers of products of cycles and graphs of order four. J. Graph Theory, 1980,4:145-155.
[67] Eggleton R B, Guy R K. The crossing number of the n-cube. Notices Amer. Math. Soc, 1970,17:757.
[68] Dean A M, Rithcter R B. The crossing number of C_4×C_4. Journal of Graph Theory, 1995, 19:125-129.
[69] Richter R B, Thomassen C. Intersections of curve systems and the crossing number of C_5×C_5. Discrete Comput. Geom., 1995, 13:149-159.
[70] Klesc M, Richter R B, Stobert I. The crossing numbers of C_5×C_n. J. Graph Theory, 1996, 22(3):239-243.
[71] Anderson M, Richter R B, Rodney P. The crossing number of C_6×C_6. Cong. Numeran-tium, 1996, 118:97-107.
[72] Anderson M, Richter R B, Rodney P. The crossing number of C_7×C_7. Cong. Numeran-tium, 1997, 125:97-117.
[73] Richter R B, Salazar G. The crossing number of C_6×C_n. Australasian Journal of Combinatorics, 2001, 23:135-144.
[74] Adamsson J. The theory of arrangement: (Ph.D. Dissertation). Ottawa,: Carleton University, 2000.
[75] Shahrokhi F, Sykora O, Szekely L A, Vrt'o I. Intersection of curves and crossing number of C_m×C_n on surfaces. Discrete Comput. Geom., 1998,19:237-247.
[76] Salazar G. On the intersections of systems of curves. Journal of Combinatorial Theory, Series B, 1999, 75:56-60.
[77] Salazar G. Drawing of C_m×C_n with one disjoint family. Journal of Combinatorial Theory, Series B, 1999,76:129-135.
[78] Salazar G. Crossing numbers of certain families of graphs: (Ph.D. Dissertation). Ottawa,: Carleton University, 1997.
[79] Juarez H A, Salazar G. Drawings of C_m×C_n with one disjoint family ii. Journal of Combinatorial Theory, Series B, 2001, 82:161-165.
[80] Adamsson J, Richter R B. Arrangements, circular arrangements and the crossing number of C_7×C_n. J. Combin. Theory, Series B, 2004, 90:21-39.
[81] Salazar G, Ugalde E. An improved bound for the crossing number of C_m×C_n: a self-contained proof using mostly combinatorial arguments. Graphs and Combinatorics, 2004, 20:247-.253.
[82] Glebsky L Y, Salazar G. The crossing number of Cm×C,, is as conjectured for n≥ m(m＋1). J. Graph Theory, 2004, 47:53-72.
[83] Jendro S, erbovà M. On the crossing numbers of S_m×P_n and S_m×C_n. asopis pro pěstovàn matematiky, 1982, 107:225-230.
[84] Kle M. On the crossing numbers of Cartesian products of paths and stars or cycles. Math. Slovaca, 1991, 41:113-120.
[85] Kle M. The crossing numbers of 5-vertex graphs with paths and cycles. Discuss. Math. Graph Theory., 1999, 19:59-69.
[86] Kle M, Richter R B, Stobert I. The crossing numbers of K_(2.3)×C_n. Discrete Mathematics, 2002, 251:109-117.
[87] Kle M, Kocǘovà A. The crossing numbers of products of 5-vertex graphs with cycles. Discrete Mathematics, 2007, 307:1395-1403.
[88] Kle M. The crossing numbers of products of paths and stars with 4-vertex graphs. J. Graph Theory., 1994, 6:605-614.
[89] Kle M. The crossing numbers of K_(2,3)×P_n and K_(2,3)×S_n. Tatra Mountains Math. Publ., 1996, 9:51-56.
[90] Kle M. The crossing numbers of K_5×P_n. Tatra Mt. Math. Publ., 1999, 18:63-68.
[91] Kle M. The crossing numbers of Cartesian products of paths with 5-vertex graphs. Discrete Mathematics, 2001, 233:353-359.
[92] 肖文兵，黄元秋．一类迪卡积图的交叉数．湖南师范大学自然科学版，2003，26(4)：3-7，17．
[93] 何小年，黄元秋．一类迪卡尔积交叉数．吉首大学学报(自然科学版)，2005，26(1)：8-11．
[94] Wang J, Huang Y Q. The crossing numbers of Cartesian products of paths with 6-vertex graphs. Journal of Jishou University(Natural Science Edition), 2005, 26(2):9-13.
[95] Peng Y H, Yiew Y C. The crossing number of P(3, 1)×p_n. Discrete Mathematics. DOI: 10.1016/j .disc .2006.03.058.
[96] 周智勇，黄元秋．笛卡尔积图K_3，3P_n的交叉数．湖南师范大学自然科学学报，2007，30(1)：31-34．
[97] Huang Y Q, YU R On the crossing numbers of P_m×W_n. Journal of Natural Science of Hunan Normal University, 2005, 28:14-16.
[98] Bokal D, Beineke L W. On the crossing number of Cartesian products with paths. J. Combinatorial Theory, Series B, 2007, 97:381-384.
[99] Kle M. On the crossing numbers of products of stars and graphs of order five. Graphs and Combinatorics, 2001, 17:289-294.
[100] Kle M. The join of graphs and crossing numbers. Electronic Notes in Discrete Mathematics, 2007, 28:349-355.
[101] Kulli V R, Akka D G, Beineke L W. On the line graphs with crossing number 1. J. Graph Theory, 1979, 3:87-90.
[102] Jendro S, Kle M. On the graphs whose line graphs have crossing number one. J. Graph Theory, 2001, 37:181-188.
[103] Akka D G, Jendro S, Kle M, Panshetty S V. On the line graphs with crossing number 1. Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat., 1997, 8:3-8.
[104] Kochol M. Construction of crossing-critical graphs. Discrete Math., 1987, 66:311-313.
[105] Geelen J F, Richter R B, Salazar G. Embedding grids in surfaces. European Journal of Combinatorics, 2004, 25:785-792.
[106] Hlinn P. Crossing-critical graphs have bounded path-width. Journal of Combinatorial Theory, B, 2003, 88:347-367.
[107] Huang J, Xu J M. The bondage numbers of graphs with small crossing numbers. Discrete Mathematics. DOI: 10.1016/j.disc.2006.09.035, 2006.
[108] Garey M R, Johnson D S. The NP-completeness column: An ongoing guide. Journal of Algorithms, 1982, 3:89-99.
[109] Hopcroft J E, Tarjan R. Efficient planarity testing. Journal of ACM, 1974, 21:549-568.
[110] Haris F C, Harris C R. A proposed algorithm for calculating the minimum crossing number of a graph, in: Proc. 8th. Quadrennial Intl. Conference on Graph Theory, Combinatorics, Algorithms and Applications. 1996.
[111] 杨元生，王丹，陆维明．四正则图的交叉数．软件学报，2002，13(12)：2259-2266．
[112] 林晓惠．图的交叉数等图论难题的研究：(博士学位论文)．大连：大连理工大学，2004．
[113] 杨元生，孙艳春，陆维明．不超过9个顶点的所有图的交叉数．小型微型计算机系统，2003，24(6)：954-958．
[114] Guy R K. Latest results on crossing nubmers. Recent Trends in Graph Theory, 1971, 1:143-156.
[115] Beineke L W, Wilson R. Selected topics in graph theory. USA: Academic Press, 1978.
[116] Archdeacon D, Richter R B. On the parity of crossing nubmers. J. Graph Theory, 1988, 12:307-310.