Regular Graph With Crossing Number

The crossing number of graph, which is an NP-complete problem, has an important theory meaning. It is put forward from practice application, and has been widely used in CAD, such as the identification and repaint of sketch map, the auto generation of ER graphs about documents in software developing tools, and DNA graphs in biology engineering.For a long time, mathematic method is used in the research of the crossing number of graph. However, if the graph is very big, the possible number of drawing will increase rapidly. Therefore, it will be very difficult to study. Consequently, there is urgent need of good algorithm for calculating the crossing number of graph.In this article, a algorithm CCN(Calculate Crossing Number) is put forward to study the crossing number. It is a very important development in graph planarity issue after planarity-determinant algorithm and embedding algorithm.By the algorithm CCN, we investigate the crossing numbers of regular graphs with small order. We get the crossing numbers of 3-regular graphs for n<16 and 4-regular graphs for n<12, and the lower bounds of the maximum crossing numbers of 3-regular graphs for n<30 and 4-regular graphs for n<19, where n is the order of graphs. According to the result, we put forward the conjecture about the maximum crossing numbers of regular graphs. We also calculate the average crossing number Aac (n) of all of the 4-regular graphs for n<12 and the average crossing number Arc(n) of some random 4-regular graphs of degree 4 for n<16. At the end of the paper, a conjecture that the average crossing number of regular graph of degree 4 is O (n2) is given.