The Crossing Number Of Pancake Graphs And Star Graphs With Small Order

The crossing number is a central notion for Topological Graph Theory with long history, which means the minimum possible number of edge crossings in a drawing of graph G in the plane. Theoretically, the crossing number is an important measure of non-planarity of a graph. In recent years, because of its applications in various fields such as wiring layout problems, VLSI theory, discrete and computational geometry, and in several other areas of theoretical computer science, the crossing number problem has been studied extensively by many mathematicians and computer scientists. However, determining the crossing number of graphs is an extremely difficult problem. Actually, Garey and Johnson proved that computing the crossing number of an arbitrary graph is NP-complete. Also, the exact crossing numbers are known only for a few families of graphs, such as the generalized Petersen graphs, Cartesian products of paths with4-vertex graphs and some graphs with small order like P(10,3),K11,Q4. In most cases, to give the upper and lower bounds is a more practical way. As to a nice drawing of a graph with the number of crossings that can hardly be decreased, it is still very difficult to prove that the number of crossings in this drawing is indeed the crossing number of the graph we studied.The pancake graph and star graph, which were proposed by Akers and Krishnameurthy in1989, possess several attractive properties than n-dimensional hypercube Qn for design of parallel architectures, such as sublogarithmic diameter, maximally fault tolerant. These properties make the n-dimensional pancake graph Pn and star graph Sn be proposed as important topology for interconnecting processors in parallel computers. Therefore, the study of the crossing number of pancake graphs and star graphs is of theoretical importance and practical value.In this paper, we combine the method of computer constructive proof with mathematical proof to study the crossing number of pancake graph P4and star graph S4. First, we give the good drawings of P4and S4based on the CCN (Calculate Crossing Number) algorithm in order to get the upper bound of the crossing number of P4and S4. Then, we give the proof of the lower bound of the crossing number of P4and S4by contradiction so that we get the crossing number of P4is exactly6and the crossing number of S4is exactly8. We also give the crossing number of S4.3and A4.3which are isomorphic to S4, and give planar drawings of some graphs with small order, such as S4,2and A4,2.