\chapter{Introduction}\label{ch1}
     \newtheorem{theorem}{Theorem}
     \newtheorem{lemma}{Lemma}

The Minimal Crossing Number problem can be defined as the determination of the minimum possible number of crossings required to connect a set of points in a plane in some defined manner. It is a problem that has intrigued investigators since its original description by Tur\'{a}n in 1944. Since the points and connections are easily represented in graphic format, the Minimal Crossing Number problem has been most commonly studied as a problem in graph theory.
	
A $graph$ is a finite nonempty set of vertices, customarily depicted as points, along with a set of unordered pairs of vertices called edges.~\cite{CHAR96} A $complete$ graph, denoted K$_n$, is one in which the edge set is complete, i.e. every vertex is $adjacent$ (connected) to every other vertex in the graph. When a graph is drawn in a plane, and the number of vertices, $n$, exceeds four, then at least two of the edges must cross each other at a point not represented by a vertex (Figure~\ref{fig:K5graph}). The problem is minimizing the number of these crossings as the number of vertices increases. A $minimal$ $K_n$ $graph$ is one that exhibits the minimal number of edge crossings possible for a graph of $n$ vertices. 
 
\begin{figure}[!ht]
       \begin{center}
       	\includegraphics[width=4.0in]{ch1/SampleK5Graph.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Minimal K$_5$ Graph Demonstrating One Crossing}
       \label{fig:K5graph}
 \end{figure} 
 
Like many NP-complete problems, the Minimal Crossing Number problem is deceptively simple and very easily stated, whereas its solution is complex. Addition of a new vertex to a minimal K$_n$ graph requires that connections be made between the new vertex and each of the existing $n$ vertices, minimizing the number of existing edges that are crossed. How can one know where in the graph to place the new vertex, and in what sequence and direction should the new edges be added? Very small complete graphs can be easily created by hand, but the complexity escalates quickly with the number of vertices. Even with all the optimizations to be presented, given a complete graph of size K$_7$, modest in size relative to the real-world problems in need of solutions, one must draw 76 graphs to exhaustively search all the possible vertex placements and edge configurations that could be used to create a minimal K$_8$. Within a few more generations of graphs, manual solutions are out of the question. From K$_8$ to K$_9$, 4590 graphs must be drawn and from K$_9$ to K$_{10}$, 56,618 graphs must be drawn~\cite{Fred06:otcnocg}. Many weeks or longer of processor time are required to perform an exhaustive search for this many graphs. Prior to the work presented here, the situation was orders of magnitude worse.
	
This thesis presents a novel method of generating minimal K$_n$ graphs.  Beginning with previous work involving exhaustive search and proceeding through several levels of optimization, we have arrived at an algorithm that allows efficient creation of all possible minimal K$_n$ graphs from minimal K$_{n-1}$. The algorithm is not specific to complete graphs, so application to other graph families is possible. 
	
The remainder of this thesis is broken down into the following sections: Chapter~\ref{ch2} provides a brief set of pertinent definitions from graph theory, following which review of the literature relevant to the Minimal Crossing Number problem is presented. Chapter~\ref{ch3} introduces our algorithm, which we have entitled Star Analysis. Both an overview of the process itself and a description of the underlying data structures and implementation details are presented. Chapter~\ref{ch4} describes the results we have obtained applying the Star Analysis algorithm to several crossing number problems. Finally, a summary and suggestions for future work are found in Chapter~\ref{ch5}. 