\chapter{Introduction}\label{chap1}
     \newtheorem{theorem}{Theorem}
     \newtheorem{lemma}{Lemma}
 
 Determining how to draw a graph in the plane with the minimum
 number of edge crossings is referred to as the crossing number problem.  
 It is generally acknowledged that the birth of the crossing number came about
 due to an experience of Paul Tur\'{a}n's while in a labor camp at a brick factory
 near Budapest, Hungary in 1944.  His story~\cite{Guy69} is as follows:
 
 \begin{quotation}
	Our work was to bring out bricks from the ovens where they were made and carry
	them on small vehicles which run on rails in some of several open stores which
	happened to be empty.  Since one could never be sure which store will be
	available, each oven was connected by rail with each store.  Since we had to
	settle a fixed amount of loaded cars daily it was our interest to finish it as
	soon as possible.  After being loaded in the (rather warm) ovens the vehicles
	run smoothly with not much effort; the only trouble arose at the crossing of
	two rails.  here the cars jumped out, the bricks fell down; a lot of extra work
	and loss of time arose.  Having this experience a number of times it occurred to me
	why on earth did they build the rail system so uneconomically;  minimizing the
	number of crossings the production could be made much more economical.[sic.]
\end{quotation}
 
 Tur\'{a}n's brick factory problem asks the question of whether the minimum number of 
 edge crossings of a complete bipartite graph of order $n$ can be determined.  Please
 refer to Section~\ref{sec:bd} for a complete listing of all
 related definitions as needed.   
 This problem proved to be extremely difficult and over the years, along with work on
 bipartite graphs, researchers explored minimizing crossings of general graphs as well
 as many other graph families.  
 
 The crossing number problem has a number of applications.  In addition to
 possible application in logistical situations like that encountered by
 Tur\'{a}n, two main areas of direct application are information display and
 circuit design.
 
 As Battista et al. state~\cite{bett99}, the visualization of complex
 conceptual structures is a key component of support tools for many
 applications in science and engineering.  Graphs are abstract structures
 used to model information thus many information visualization systems
 require graphs to be drawn so they are easy to read and understand.  Minimizing
 the crossings of the edges of these graphs makes them easier to read as well
 as more esthetically pleasing.  Those interested in exploring graph visualization
 are referred to~\cite{bett94:adgab} and~\cite{bett99}.
 
 The crossing number problem has also found application in the area of Very Large
 Scale Integration (VLSI) circuit technology. Leighton~\cite{lei83,lei84:nlbtvlsi}
 shows the relevance of crossing numbers to the problem of reducing chip layout area and
 minimizing chip size.  Area and size reduction lower production costs and allow for more
 reliable performance of larger chips.  He showed the close
 relationship between the crossing number and the bisection width of a graph.  
 Both bisection width and the crossing number are important properties of graphs that affect 
 minimum layout area for VLSI design. 

 Finding the exact value for crossing numbers is not an easy task. The difficult nature
 of determining the exact value of the crossing number of a complete graph of order $n$, 
 denoted $\nu (K_{n})$, even for small
 values of $n$ is illustrated by the small amount of literature from the early 1960's to date
 ~\cite{Egg73:cng,fyh:atsrrfctcnok,Guy60:acp,Guy69,Guy72:cng,hh63:noccg,
 hh96:apafctmcnoag,Tadj98:pcgvmcng,th97:pcmcng,ymfh:agqs}.  But, this
 is not a reason to leave the problem for estimates only.  Being able to determine the
 exact crossing number of a graph and having access to graphs with this number of crossings
 will allow researchers to thoroughly investigate the nature of these graphs.  Information
 may lie within the structure of these minimal graphs that will bring new insight into 
 minimal graphs in general.  Work by Aichholzer et al. 
 ~\cite{ak01:aoteanrotrcn,ahn01:otnoteppsmh,ak01b:tpsotdbacoaar,ak05:eotfspswa} is
 a good example of where computational experiments, performed with
 care and in combination with a theoretical basis, help shed light on difficult combinatorial
 problems.
 
 This dissertation addresses the crossing number problem as related to complete graphs, though
 the process introduced is anticipated to be directly applicable to other graph
 families (bipartite, general, etc.) with little or no modification.  
 
 The contribution to the crossing number problem is the creation of a functional, constructive 
 technique for building minimal complete graphs   
 of order $n$ from minimal complete graphs of order $\it{n-1}$.  This technique allows for the
 construction of all representative graphs of minimal K$_n$ grown from minimal 
 K$_{n-1}$.  All isomorphic families available from this growth pattern will be available for
 enumeration and drawing as well as topological, spectral, and other desired analysis.     
 
 The remainder of this dissertation is structured as follows: Chapter~\ref{chap2} 
 presents basic definitions and background information on graphs including a survey
 of the related literature. Description of
 the algorithm from which thiw work begins, along with its shortfalls are 
 addressed. Chapters~\ref{chap3} and~\ref{chap4} present the growth of K$_n$ stepping through the new ideas
 and relevant proofs that allow for functional calculation of minimal K$_n$ from minimal K$_{n-1}$.
 A summary of improvements achieved, due to search space restrictions and a new technique, in 
 addition to
 results attained to date in growing minimal K$_{n}$ are discussed in Chapter~\ref{chap5}. 
 Conclusions and a look at open 
 problems that have presented themselves, including new conjectures related to minimal 
 K$_{n}$, appear in Chapter~\ref{chap6}.
 