\chapter{Results}\label{ch4}
 
\section{Complete Graphs}\label{sec:resultsKn}
{
The Star Analysis process represents a total departure from the exhaustive search method. Beginning with Harris and Harris and progressing up to this point, each improvement built upon the work that had gone before without changing the underlying algorithm, apart from optimizing the search space. With Star Analysis, we started from the ground up, so our first concern was assuring that the process worked correctly. Therefore, we began our Star Analysis test runs on the complete K$_n$ graphs generated previously by the processes described in Chapter~\ref{ch2}. Recall that graphs up to $n = 9$ were generated by the parallel processing method with basic region restriction. K$_{10}$ graphs were generated with radical region restriction, the most optimized system prior to Star Analysis. By repeating the process using the Star Analysis module, we would be able to confirm that the same number of total graphs, regions per graph, and isomorphic families were being generated. We also of course confirmed that the same crossing numbers were obtained (Table~\ref{tbl:rrrVSsa}). "Region Restriction" in the table refers to either basic or radical, depending on data availability.

 \begin{table}[h]
	\centering
		\begin{tabular}{|c|ccccccc|} \hline
	$n$ 		         &  5 & 6 &  7 &  8 &    9 &    10 & 11   \\ \hline
	Total Graphs		       	\\ \hline
	Region Restriction     & 12 & 4 & 76 & 20 & 4,590 & 56,618 & *       \\ \hline
	Star				& 12 & 4 & 76 & 20 & 4,590 & 56,658 &  *			\\ \hline
	Iso Families                                              \\ \hline
	Region Restriction     & 1 & 1 & 5 & 3 & 1,453 & 5,679 & *           \\ \hline
	Star				& 1 & 1 & 5 & 3 & 1,453 & 5,679 & *						\\ \hline
	Number of Regions 			           												\\ \hline
	Region Restriction     & 8 & 14 & 25 & 40 & 65 & 97 &  *                \\ \hline
	Star        & 8 & 14 & 25 & 40 & 65 & 97 &  146								\\ \hline
	Crossing Number                                           \\ \hline
	Region Restriction     & 1 & 3 & 9 & 18 & 36 & 60 & *                \\ \hline
	Star        & 1 & 3 & 9 & 18 & 36 & 60 & 100              \\ \hline
		\end{tabular}
	\caption{Comparison of Results with Region Restriction and Star Analysis for K$_{n}$}
	(* = did not complete running)
	\label{tbl:rrrVSsa}
\end{table}
   
A minor discrepency occurred at K$_{10}$; the same number of isomorphic families  and regions were found, but there was a slightly greater number of total graphs generated with Star Analysis than with Parallel/Region Restriction. This discrepency remains unresolved, but we are reviewing the graphs generated by Star Analysis to see where the extra graphs occur. This issue does not affect the progression from K$_{10}$ to K$_{11}$, since all isomorphic families are available to provide feeder graphs, but should nonetheless be resolved. 

Table~\ref{tbl:runtimesradvsstar} shows the timing results of these test runs as compared with the results from parallel processing/radical region restricton from ~\cite{Fred06:otcnocg}. Time approximations for Star Analysis are based on the processes of Path List generation, crossing number determination, and building all possible minimal grafts, with the exception of K$_{11}$, where graph building is not included. Radical Region Restriction times do not include running through isomorphic testing, so that portion of the time is excluded from Star Analysis as well. Also bear in mind that Star Analysis is running on a single processor, whereas Radical Region Restriction is running in parallel on multiple processors. 

 \begin{table}[h]
	\centering
		\begin{tabular}{|c|cccc|} \hline
	$n$      & 8 & 9 & 10 & 11                           \\ \hline
	Radical  & 5 min & 8 min & 1 week & *               \\ \hline
	Star     & $< 1$ sec & 27 sec & 108 min & 62 hr   \\ \hline
		\end{tabular}
	\caption{Runtimes to Generate Minimal K$_{n}$}
	(* = did not complete running)
	\label{tbl:runtimesradvsstar}
\end{table}   

For the larger values of $n$, $NAUTY$ became the rate-limiting step in the Star Analysis process. We were able to generate the Path Lists and obtain the value for minimal crossing number relatively quickly. Table~\ref{tbl:nonauty} shows the approximate times for all the processes in Table~\ref{tbl:runtimesradvsstar} plus isomorphic testing by $NAUTY$. $NAUTY$ is reputed to be the fastest iso-testing program available, but improvements in processing time here would be most welcome. 

 \begin{table}[h]
	\centering
		\begin{tabular}{|c|cccc|}            \hline
	$n$ 		& 8 & 9 & 10 & 11              \\ \hline
	Runtime & 3 sec & 12 min & 62 hr &  pending \\ \hline
		\end{tabular}
	\caption{Star Analysis Runtimes With Isomorphic Testing By $NAUTY$}
	\label{tbl:nonauty}
\end{table}   

We discovered one interesting and, to our knowledge, not previously reported phenomenon as we progressed from $n$ = 5 to $n$ = 11. In all cases when a K$_{n-odd}$ graph was grown from the previous K$_{(n-1)-even}$, a minimal graph could be obtained with new vertex placement in every region. This was not the case for any instance of K$_{(n-1)-odd}$ to K$_{n-even}$. In other words, there were one or more regions in all K$_{(n-1)-odd}$ graphs that did not grow any minimal K$_{n-even}$ graphs when the new vertex $n$ was placed in them. We don't have an explanation for this phenomenon, but feel it merits further investigation.    

Finally, we present the results from a test of the crossing number of a K$_{11}$ graph. The crossing, $\nu$(K$_{11}$), of 100 verifies Guy's Conjecture for $n$ = 11. A single instance of a minimal K$_{11}$ graph is shown in Figure~\ref{fig:K11}.

\begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=5.0in]{ch4/K11Chap4.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{One Instance of a Minimal K$_{11}$ Graph [J. Fredrickson~\cite{Fred06:otcnocg}]}
       \label{fig:K11}
\end{figure}  

%\end section {Complete Graphs}

\section{Complete Bipartite Graphs}\label{sec:resultsKnm}
{
One of our objectives in building the Star Analysis module was to create a system that could be generally applied to multiple graph families. From the perspective of Star Analysis, it is merely creating paths based on the Path List delivered to it. It neither knows nor cares whether those paths are generating a complete graph, a less-than-complete graph, or a graph of an entirely different type. In order to demonstrate proof of concept, our second series of tests were run to grow complete bipartite graphs and determine their crossing numbers. 

One adjustment that was required to switch from complete graphs to complete bipartite graphs was that the program-calling scripts had to be revised in order to create, for example, edges-to-add lists that were specific to the new format. The process was run first for a family of bipartite graphs, K$_{3,3}$ through K$_{3,10}$. The starting K$_{3,2}$ graph was generated by hand and the starting input file was created manually. Thereafter, the scripts took over and ran each family member in succession, progressing from $n = 4$ to $n = 10$. No modification of the actual Star Analysis program was required. In order to minimize running time for this trial, we did not generate all isomorphic families above K$_8$. 

The results of the first test are shown in Table~\ref{tbl:bipartite}. All crossing numbers match those previously reported, as well as confirming Zarankiewicz' conjecture.
 
 \begin{table}[h]
	\centering
		\begin{tabular}{|c|cccccccc|} \hline
	$n$ 		         & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10       \\ \hline
	Crossing Number  & 1 & 2 & 4 & 6 & 9 & 12 & 16 & 20  \\ \hline
		\end{tabular}
	\caption{Crossing Numbers Found by Star Analysis for K$_{3,n}$}
	\label{tbl:bipartite}
\end{table}        

Interestingly, the phenomenon described for K$_{n-even}$ growing to K$_{n+1-odd}$ graphs, in which minimal graphs were found with new vertex placement in every region, was also seen growing bipartite graphs. In the bipartite case, the situation was a bit more complicated. Given K$_{m,n}$, minimal graphs could be created when progressing from $n$-even to $n$-odd when $m$ was held comstant, irrespective of whether $m$ was odd or even. In other words, for a family of graphs such as the K$_{3,n}$ family seen in Table~\ref{tbl:bipartite}, every other generation, specifically when $m$ was even,  consisted of graphs in which new vertex placement in each region resulted in minimal graphs in the next generation    
 
}%\end section{Complete Bipartite Graphs}
%\end chapter(Results)
\newpage 	        
 
 
 