\chapter{Conclusions and Future Work}\label{ch5}
 
\section{Summary and Conclusions}\label{summary}
{
We present a new approach to the generation of minimal graphs based on analysis of independent paths between vertices. Our process grows minimal K$_n$ graphs from minimal K$_{n-1}$ with a process we have entitled Star Analysis. Using minimal K$_{n-1}$ as a template, independent shortest paths are created from newly added vertex $n$ to each of the original $n-1$ vertices.  Uncoupling the process of shortest path creation from graph drawing efficiently determines the minimal crossing number of the graph without the overhead of lengthy procedures to lay down edge segments.  Graphs to be drawn can then be selected from the resulting Path List, and only desired graphs are drawn, as opposed to previous methods where all possible graphs were drawn until they exceeded the minimum.  The result of eliminating the unnecessary partial graph drawing is a substantial reduction in processing time. All other optimizations with respect to restriction of regions through which paths are drawn are maintained in the current system and contribute to the improved results.

Prior to this work, the largest confirmed minimal crossing number was for complete graphs of order $10$. We have confirmed that the minimal crossing number for K$_{11}$ is 100, which satisfies Guy's conjecture.  We are eager to pursue graphs of higher order to see if the conjecture holds for $n > 11$. 

We have also shown that our Star Analysis process can be applied to other families of graphs. Specifically, we have used it to generate minimal bipartite graphs. As in the complete graph family, these graphs are grown from minimal K$_{m,n-1}$ to minimal K$_{m,n}$. We have been able to confirm Zarankiewicz' conjecture for graphs as large as K$_{?,?}$.
}%\end section {Summary and Conclusions}

\section{Future Work}\label{futwork}
{
We have come a long way since the original algorithm for finding the minimal crossing number of a complete graph was devised~\cite{hh96:apafctmcnoag}, but much work remains. Despite all optimizations, creating minimal graphs of large $n$ remains a formidable challenge. Further optimization of the process is clearly required to progress on into uncharted territory. 

The first obvious optimization is to return to parallel processing. We believe that with the current method, we can eliminate the queuing system and all its message passing overhead. The reason for this is that the Star Analysis module is well suited to static partitioning. Previous search methods either statically divide the search space among processors, resulting in unbalanced search trees and their corresponding unbalanced processor loads, or split creation of individual graphs among processors, resulting in huge overhead.  Star Analysis allows Path Lists to be created for individual graphs independent of each other. Each processor can be assigned a single graph from one isomorphic family to process, and the processing time should be roughly the same. Using multiple processors should improve processing time sufficiently to progress to higher order graphs, $n > 11$.

A second optimization is suggested by the finding we described in Chapter 4 that when growing minimal K$_n$ for odd values of $n$, minimal graphs can be created with new vertex placement in every region of K$_{n-1}$, whereas that is not the case creating minimal $n$ even graphs. Further analysis of this phenomenon, if it persists with increasing $n$, might reveal a way to eliminate regions from consideration in placement of the new vertex, further reducing the search space. It is also possible that other features of graph substructure might lend themselves to similar optimizations.

Another avenue of exploration suggested by the above involves the case of graphs that are locally but not globally minimal, in other words, graphs that are minimal based upon the chosen region for vertex placement, but that do not generate the global minimal crossing number. Further analysis of these graphs could provide insight into the substructural arrangements of minimal versus non-minimal graphs, perhaps providing further opportunities for search space reduction. 

Finally, the question remains whether it is possible to generate minimal K$_n$ from non-minimal K$_{n-1}$. All the minimal K$_n$ graphs created by Star Analysis are grown from minimal K$_{n-1}$. It is theoretically possible that some minimal graphs are therefore not being generated by our system. One approach to this problem is to take all the minimal-plus-one K$_{n-1}$ paths created by Star Analysis, use them to generate graphs, and then create a K$_n$ Path List. We can then discover if any of the paths so generated achieve the previously determined minimal crossing number. It is our belief that no such graphs will be found, but this remains to be proven.      
}%\end section{Future Work}
%\end chapter {Conclusions and Future Work}