Some Results Of The Crossing Numbers Of Graphs

The crossing number of a graph is an active and important subject in topological graph theory. It is an important topological measure for graphs. Crossing numbers play a key role in various fields of discrete and computational geometry and they can also be used in discussing the maximal planar subgraphs [30] and obtaining lower bounds on the chip area required for the VLSI circuit layout of a graph[27]. However, evaluating the crossing number of a graph is a difficult work and little is known about it. In view of the complexity, deciding the crossing number of a graph is in the NP-complete class[16]. Some results on the crossing number will be given in the thesis:1. Giving the exact value of the crossing number of the circular graph C(m, 3);2. Giving the exact value of the crossing number of the circular graph C(ik, 4);3. Giving some results of the crossing number of two planar graphs.