On The Crossing Number Of Graphs

The crossing number of a graph is the minimum number of pair-wise intersection of edges in a drawing of in the plane,denoted cr(G).It is well known that the crossing number of a graph is attained only in good drawings of the graph,which are those drawings where: ( 1 ) no two edges intersect each other more than once ( 2 ) no edge has a self-intersection ( 3 ) no two adjacent edges intersect ( 4 ) each intersection of edges is a crossing rather than tangential.Computing the crossing number of a given graph has been proved to be NP-complete.It is very difficult to determine the exact crossing number of a given graph for its complicity. The crossing number problem has been studied for complete graph,complete n-partite graph,Circular graph,generalized Petersen graph and Cartesian graph.The crossing number of few families of graphs are known so far,most of which are Cartesian Products of special graphs,such as Cartesian Products of paths,cycles or stars with "small" vertex graphs.There are two chapters in the thesis:The first chapter introduces the basic definition, and some known results.In the second chapter, we will present some new results:The crossing number of two Circular graphs C(11,4) and C(13,4).The crossing number of two Cartesian products.The crossing number of a tripartite graph.