The Crossing Number Of Circular Graphs

This paper mainly studies the crossing number of several special graphs. A graph is plane if and only if its crossing number is zero. So the crossing number is an important topological property of a graph. However, compared with other graph theories, the study on crossing number has been much less systematical.There are two main reasons for this:one is that it is very difficult to determine the crossing number of a general graph.In [36],Garey and Johnson have proved that it is NP-hard to determine the crossing number for an arbitrary graph.The other reason is that we rely much on the special structures of the graphs when we study them which makes it hard to generalize.Based on many results on crossing number,we focus on the crossing number of a type of circular graphs and obtain the following results:(1) The crossing number of C(3m, m)is m(m≥3).(2)The crossing number of C(16,4)is 8.