\chapter{Background}\label{chap2}
 
 In this chapter we present the basic definitions needed for reading this dissertation.  All
 background definitions are collected in Section~\ref{sec:bd}.  Section~\ref{sec:brl} 
 covers the history and related work on crossing numbers with the main focus on the crossing
 number of complete graphs.  A brief overview of graph isomorphism is given in Section 
 ~\ref{sec:gi} as it relates to our needs.  Finally Section ~\ref{sec:es} describes the
 exhaustive search algorithm our new research initiated from in detail. This allows for
 clear understanding as we move forward in growing minimal K$_{n}$ from minimal K$_{n-1}$.
  
 \section{Basic Definitions }\label{sec:bd}
 {
 There are several books available on graph theory. ~\cite{CHAR96} and ~\cite{West96} are 
 two that each have a small section dedicated to crossing numbers.  The basis for the
 definitions in this chapter come from~\cite{CHAR96}.
 
 \newtheorem{definition}{Definition}

 \begin{definition}\label{def:graph}
 A simple \textbf{graph} G is a finite nonempty set of object called {\it vertices} together with a set
 of unordered pairs of distinct vertices of G called {\it edges}.
 \end{definition}
 
 The vertex set of G is denoted V(G) and the edge set is denoted E(G).  Throughout this
 dissertation, all graphs are simple unless otherwise noted.
 
 Given two vertices, {\it u} and {\it v}, of graph G, the edge {\it e=(u,v)} joins {\it u} 
 and {\it v}.  Common notation
 for the edge {\it e=(u,v)} is {\it uv}.  We use this more convenient notation.  If {\it e = uv}
 is an edge of G, then {\it u} and {\it v} are called {\it adjacent} vertices, {\it u} and {\it e} 
 are {\it incident} as are
 {\it v} and {\it e}.  If $e_{1}$ and $e_{2}$ are distinct edges of G with a common vertex we say
 that $e_{1}$ and $e_{2}$ are adjacent edges.   
 
 \begin{definition}\label{def:order}
 The \textbf{order} of graph G is the cardinality of the vertex set of G, commonly 
 denoted \it{n}(G) or {\it n}.  
 \end{definition}
 
 \begin{definition}\label{def:size}
 The \textbf{size} of graph G is the cardinality of the edge set of G, commonly 
 denoted {\it m}(G) or {\it m}.  
 \end{definition}
 
 \begin{definition}\label{def:degree}
 The \textbf{degree} of a vertex {\it v} is the number of edges incident with {\it v},
 commonly denoted deg {\it v}.
 \end{definition}


Referring to Figure~\ref{fig:graph}...
\begin{figure}[!ht]
       \begin{center}
       		graph with above terms illustrated
       		       \vspace*{2in}
         %\includegraphics[width=1.0in]{ch3/unbalanced}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{A Graph Described}
       \label{fig:graph}
 \end{figure} 
 
 \begin{definition}\label{def:iso}
 A graph G is \textbf{isomorphic} to graph H if there exists a one-to-one mapping
 $\phi$, called an \textbf{isomorphism}, from V(G) onto V(H) such that $\phi$ preserves
 adjacency; i.e. {\it uv} $\in$ E(G) if and only if $\phi${\it (u)} $\phi${\it (v)} $\in$ E(H).
 \end{definition}
 
 The two graphs (a) and (b) of Figure~\ref{fig:iso}
 \begin{figure}[!ht]
       \begin{center}
       		3 graphs 2 iso - one not
       		       \vspace*{2in}
         %\includegraphics[width=1.0in]{ch3/unbalanced}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Isomorphic and Nonisomorphic Graphs}
       \label{fig:iso}
 \end{figure}
 
 \begin{definition}\label{def:subgraph}
 A graph G is a \textbf{subgraph} of graph H if V(G) $\subseteq$ V(H) and E(G) $\subseteq$ E(H).
 \end{definition}
 
 \begin{definition}\label{def:complete}
 A graph G is a \textbf{complete}  if every two of its vertices are adjacent. The notation for
 the complete graph of order $n$ is K$_{n}$.
 \end{definition}
 
 In Figure~\ref{fig:Knsub} the graph of the left is a complete graph with six vertices...
 
 \begin{figure}[!ht]
       \begin{center}
       		K6 and two subgraphs K5 and something not complete
       		       \vspace*{2in}
         %\includegraphics[width=1.0in]{ch3/unbalanced}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{A Complete Graph and Two Subgraphs}
       \label{fig:Knsub}
 \end{figure} 
 
 \begin{definition}\label{def:kpartite}
 A graph G is a \textbf{k-partite}, k$\geq 1$, if it is possible to partition V(G) into $k$
 subsets V$_{1}$,V$_{2}$,...,V$_{k}$, called partite sets, such that every element of
 E(G) joins a vertex of V$_{i}$ to a vertex of V$_{j}$, $i\neq j$.
 \end{definition}
 
 \begin{definition}\label{def:compkpartite}
 A \textbf{complete k-partite} graph G is a $k$-partite graph with partite sets 
 V$_{1}$,V$_{2}$,...,V$_{k}$ having the additional property that if $u\in$ V$_{i}$
 and $v\in$ V$_{j}$, $i\neq j$, the $uv\in$ E(G). 
  \end{definition}
   
  The {\it complete bipartite graph} consists of two partite sets of order $m$ and $n$
  is denoted K(n,m) or K$_{n,m}$.  The graph K$_{1,n}$ is called a {\it star}.
  
  
  A complete bipartite graph illustrating the ``brick factory problem" is seen in 
  Figure~\ref{fig:bipart}.
  
  \begin{figure}[!ht]
       \begin{center}
       		a bipartite figure illustrating the brick factory problem
       		       \vspace*{2in}
         %\includegraphics[width=1.0in]{ch3/unbalanced}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{A Bipartite Graph Representation of Tur~\'{a}n's Brick Factory Problem}
       \label{fig:bipart}
 \end{figure}
 
  \begin{definition}\label{def:cartprod}
  The \textbf{cartesian product} graph F = G $\times$ H has V(F) = V(G) $\times$ V(H), and two
  vertices ($u_{1},u_{2}$) and ($v_{1},v_{2}$) are adjacent iff either $u_{1}=v_{1}$
  and $u_{2}v_{2}\in$ E(H), or $u_{2}=v_{2}$ and $u_{1}v_{v}\in$ E(G).  
  \end{definition}
  
   \begin{definition}\label{def:walk}
  A \textbf{u-v walk} of gaph G is a finite, alternating sequence
  	\center
  	$u=u_{0},e_{1},u_{1},e_{2}...,u_{k-1},e_{k}=v$
  	\endcenter
  	of vertices and edges, beginning with vertex $u$ and ending with vertex $v$,
  	such that $e_{i}=u_{i-1}u_{i}$ for $i$ = 1, 2, ..., $k$.  The length of the walk
  	is denoted by $k$.
  \end{definition}
  
  A $u-v$ path is a $u-v$ walk in which no vertex is repeated.
  
   \begin{definition}\label{def:connected}
  A vertex $u$ is \textbf{connected} to vertex $v$ in graph G if there exists a $u-v$
  path in G.  A graph G is connected if every two of its vertices are connected.
  \end{definition}
  
  It should be obvious that every complete graph, K$_{n}$ is connected.
  
  \begin{definition}\label{def:bisecwidth}
  The \textbf{bisection width} of a graph is the minimum number of edges which must be
  removed from the graph in order to disconnect it into two equal-sized pieces.
  Two pieces are equal-sized if the number of vertices in each differs by no
  more than one. Standard notation bw(G). 
  \end{definition}

	Figure~\ref{fig:biwidth} shows a graph G with its bisection width... 
 \begin{figure}[!ht]
       \begin{center}
       		a bisection width example
       		       \vspace*{2in}
         %\includegraphics[width=1.0in]{ch3/unbalanced}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{The Bisection Width of a Graph}
       \label{fig:biwidth}
 \end{figure}
  
  The cutwidth problem is to arrange vertices in a line so that the maximum number
  of edges crossing the ith place, for all i, is minimized.
 
  \begin{definition}\label{def:cutwidth}
  The \textbf{cutwidth} of a graph G with vertex set V,edge set E, and injection
  $\phi:V\leftarrow$ \{1,2,3,...,$|V|$\} is defined as
  \center
   \[cw(G) = \min_{\phi}\max_{i}|\{uv\in E:\phi(u)\leq i < \phi (v)\}| \].    
  \end{definition}
 
 The illustration if Figure~\ref{fig:cutwidth} aids in explaining the cutwidth...
 
 \begin{figure}[!ht]
       \begin{center}
       		a cutwidth example
       		       \vspace*{2in}
         %\includegraphics[width=1.0in]{ch3/unbalanced}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{The Cutwidth of a Graph}
       \label{fig:cutwidth}
 \end{figure} 
 
   \begin{definition}\label{def:embeddable}
  A graph G with order $n$ and size $m$ is \textbf{realizable}
  or \textbf{embeddable} on a surface S if it is possible to distinguish a 
  collection of $m$ curves, pairwise disjoint except possibly for endpoints, on S 
  that correspond to the edges of G such that if a curve A corresponds to the
  edge $e=uv$, then only the endpoints of A correspond to vertices of G, namely
  $u$ and $v$.
  \end{definition}
  
  \begin{definition}\label{def:planar}
  A graph is \textbf{planar} if it can be embedded in the plane.  
  \end{definition}
  
  Embedding a graph in the plane is equivalent to embedding it on the sphere.  
  Perform stereographic projection to see this relationship.
  
  \begin{definition}\label{def:plane}
  A planar graph that is embedded in the plane is called a \textbf{plane} graph.  
  \end{definition}
 
 
 \begin{figure}[!ht]
       \begin{center}
       		planar and plane graph
       		       \vspace*{2in}
         %\includegraphics[width=1.0in]{ch3/unbalanced}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{A Planar and Plane Graph}
       \label{fig:plane}
 \end{figure}
  
  \begin{definition}\label{def:region}
  Given a plane graph G, a \textbf{region} of G is a maximal portion of the plane
  for which any two points may be joined by a curve A such that each point of A
  neither corresponds to a vertex of G nor lies on any curve corresponding to
  an edge of G.  
  \end{definition}
  
  Think of the regions of G as the disjoint portions of the plane remaining after
  all the edges and vertices have been removed.
  
  \begin{definition}\label{def:boundary}
  The \textbf{boundary} of a region $R$ of a plane graph G consists of all points $x$
  corresponding to vertices and edges of G having the property the $x$ can be joined 
  to a point of R by a curve, all of whose points differ from $x$ belong to $R$.  
  \end{definition}
  
 \begin{figure}[!ht]
       \begin{center}
       		the regions and boundary of a graph 
       		       \vspace*{2in}
         %\includegraphics[width=1.0in]{ch3/unbalanced}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{The Regions and Their Boundaries of K$_{4}$}
       \label{fig:regbound}
 \end{figure}
  
  We relate the order, size, and number of regions of any connected plane graph with
  Euler's Formula, stated in Theorem ~\ref{thm:Euler}.
  
  \begin{theorem}\label{thm:Euler}[Euler's Formula]
  If G is a connected plane graph with n vertices, m edges and r regions, then
  \center
  n - m + r = 2.
  \endcenter
  \end{theorem}
  
  It follows from Theorem~\ref{thm:Euler} that every two embeddings of a connected planar
  graph in the plane result in plane graphs with the same number of regions.  This
  allows us to talk of the number of regions of a connected planar graph. 
 
  F\'{a}ry~\cite{fary48:slrpg} is know for the earliest result concerning the drawing
  of a graph in the plane.
  He showed that every planar graph can be embedded in the plane so that every edge is
  a straight line segment.  In terms of crossing numbers this implies that if $\nu(G)=0$
  then $\bar{\nu}(G)=0$.
 
  Nonplanar graphs cannot be drawn in the plane; some edges must cross. This leads us
  to define the crossing number of a graph, a standard measure of graph nonplanarity.
  
  \begin{definition}\label{def:crossing}
  The \textbf{crossing number} $\nu(G)$ of a graph G is the minimum number of edge crossings
  among the drawings of G in the plane.  
  \end{definition} 
  
  With the introduction of the word `drawing' it is best examine the standard definition
  of a good drawing:
  
  \begin{definition}\label{def:good drawing}
  A \textbf{good drawing} of a graph G satisfies the following:
  \begin{itemize}
    \item adjacent edges never cross 
  	\item two nonadjacent edges cross at most once 
  	\item no more than two edges cross at a point of the plane 
  	\item no edge passes through a vertex of the graph G
  \end{itemize}
  \end{definition}  

\begin{figure}[!ht]
       \begin{center}
       		good drawing nonos
       		       \vspace*{2in}
         %\includegraphics[width=1.0in]{ch3/unbalanced}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Good Drawing of a Graph}
       \label{fig:good}
 \end{figure}
 
  \begin{definition}\label{def:minimal}
  A \textbf{minimal graph} G is a graph with the minimum number of edge crossings
  among the drawings of G.  
  \end{definition} 
 
  \begin{definition}\label{def:rectilinear crossing number}
  The \textbf{rectilinear crossing number} of a graph G, denoted $\bar{\nu}(G)$, is the 
  minimum number of edge crossings among all drawings of G in the plane in which
  each edge is a straight line segment.
  \end{definition} 
 
 
  The following definitions are relevant to the discussion in Section~\ref{sec:eres} of
  Edmond's Rotational Embedding Scheme.
  
  A compact orientable 2-manifold is a surface that we can think of as a sphere with
  attached handles.  The number of handles is referred to as the genus of the surface.
  
  \begin{definition}\label{def:genus}
  The \textbf{genus} of a graph G is the smallest genus of all surfaces on which G
  can be embedded. Genus of a graph is denoted gen(G).  
  \end{definition}
  
  Since, as mentioned, the embeddings of graphs on planes or spheres is equivalent, the
  graphs of genus 0 are exactly planar graphs.  In this dissertation we are only concerned with
  graphs of genus 0. 
  
    \begin{definition}\label{def:2-cell}
  A region of a graph G is a \textbf{2-cell} if any simple closed curve in that region can
  be continuously deformed or contracted in that region to a single point. 
  \end{definition} 
  
  Every region of a connected graph embedded on the sphere is a 2-cell, however this may
  not be the case for connected graphs embedded on surfaces of positive genus.
  
    \begin{definition}\label{def:2-cell embedding}
  If all the regions of a graph G embedded on a surface S are 2-cells, the embedding is called
  a \textbf{2-cell embedding}. 
  \end{definition} 
  
  
  Via an extension of Euler's Formula (Theorem~\ref{thm:Euler}), it can be noted that every  
  embedding of a connected graph G on a surface of genus Gen(G) result in the same
  number of regions.
    
 } % end \section{Basic Definition}
 
 
 
 
 
 
 
 
 
 	
 \section{Background and Related Literature}\label{sec:brl}
 {
 
 This section discusses the background of crossing numbers and provides a brief survey
 of the relevant literature. The main
 focus is on the crossing number of complete graphs.  The crossing number problem, being
 so difficult to attack in general, has followed many splintered paths as 
 individuals have attempted to advance from different perspectives.  There are many 
 results with not a great deal of generalization evident.  Bits and pieces have 
 been proven over a wide variety of graph families and different types of edge 
 crossings.  We begin with an overview of the crossing number of complete graphs 
 in Section~\ref{sec:cncg}.  Section~\ref{sec:ocn} briefly looks at the work 
 being done on other types of crossing numbers and other graph families being explored.
  We conclude the section with an overview of graph 
 isomorphism, as it relates to our needs, in Section~\ref{sec:gi}.  
 
 
\subsection{The Crossing Number of Complete Graphs }\label{sec:cncg}
 {
 
 As mentioned in the Chapter~\ref{chap1}, Tur\'{a}n's ``Brick factory problem'' 
 asks the question of finding the crossing
  number of a complete bipartite graph.  
  Zarankiewicz~\cite{Zara:ptcg} proposed a solution to the problem in 1953. 
  Guy~\cite{Guy69:dafozt}points out an error in Zarankiewicz's proof that was discovered in 1965 by
  Kainen and Ringel and shared with Guy via private communication.  The error was the assumption as part
  of a deduction  that among the {\it m} graphs K$_{m,1}$ that compose K$_{m,n}$ it is always
  possible to find two which do not contain a crossing.  To date,
  Zarankiewicz's conjecture has not been proven or disproven and stands as an upper bound.
  

  \begin{theorem}\label{th:Z}[Zarankiewicz]
	The crossing number of the complete bipartite graph satisfies the inequality
	
\begin{center}
 $\nu$(K$_{m,n}$)$\leq$ $\left\lfloor \frac{m}{2}\right\rfloor\left\lfloor \frac{m-1}{2}\right\rfloor
  \left\lfloor \frac{n}{2}\right\rfloor\left\lfloor \frac{n-1}{2}\right\rfloor$.
\end{center}
	\end{theorem}
	
	\newtheorem{conjecture}{Conjecture}
	\begin{conjecture}\label{cj:Z}[Zarankiewicz]
	The crossing number of the complete bipartite graph satisfies the equality
	\begin{center}
	$\nu$(K$_{m,n}$)= $\left\lfloor \frac{m}{2}\right\rfloor\left\lfloor \frac{m-1}{2}\right\rfloor
  \left\lfloor \frac{n}{2}\right\rfloor\left\lfloor \frac{n-1}{2}\right\rfloor$.
  \end{center}
  \end{conjecture}
    
  In 1960, Guy~\cite{Guy60:acp} popularized the search for the crossing number
  of a complete graph with the introduction of an upper bound, confirmed by 
  Blazek and Koman~\cite{bk64:mpccpg}.  He mentions that Erd\"{o}s had been looking
  at the problem for at least twenty years prior to this.  No improved upper bound
  has been published to date.
 
  \begin{theorem}\label{th:Kn}[Guy]
	The crossing number of the complete graph satisfies the inequality
\begin{center}
  $\nu$(K$_{n}$)$\leq \frac{1}{4}\left\lfloor \frac{n}{2}\right\rfloor\left\lfloor 
  \frac{n-1}{2}\right\rfloor
  \left\lfloor \frac{n-2}{2}\right\rfloor\left\lfloor \frac{n-3}{2}\right\rfloor$.
\end{center}	
	\end{theorem}
	
	Another representation of the inequality in Theorem~\ref{th:Kn} is:
	
\begin{center}
  $\nu$(K$_{n}$)$\leq\frac{1}{64}n(n-2)^{2}(n-4)$,   for n even,\\
  $\nu$(K$_{n}$)$\leq\frac{1}{64}n(n-1)^{2}(n-3)^2$,  for n odd.
\end{center}
 
	It it interesting to note that if equality holds for Theorem~\ref{th:Kn} for {\it n} odd, then by 
	a straightforward induction proof it can be shown to hold for the next value of {\it n}(even).  
	We cannot make the inductive step from even to odd.  As Guy says, ``we are trying to walk,
	using only one leg". This same one legged induction holds for the inequality in 
	Theorem~\ref{th:Z}~\cite{Guy72:cng}. 
	
	It has been conjectured~\cite{Guy60:acp,hh63:noccg} that equality holds in 
	Theorem~\ref{th:Kn} for all {\it n}.
	This conjecture, made in the early 1960's, has not been proven or disproven to date.
	
	\begin{conjecture}\label{cj:Kn}[Guy~\cite{Guy60:acp},Harary and Hill~\cite{hh63:noccg}]
	The crossing number of the complete graph satisfies the equality
	\begin{center}
	$\nu$(K$_{n}$)$= \frac{1}{4}\left\lfloor \frac{n}{2}\right\rfloor\left\lfloor \frac{n-1}{2}\right\rfloor
  \left\lfloor \frac{n-2}{2}\right\rfloor\left\lfloor \frac{n-3}{2}\right\rfloor$.
  \end{center}
  \end{conjecture}
  
  In 1963, Harary and Hill mention the rectilinear crossing number, denoted $\bar{\nu}$(K$_{n}$)
  for complete graphs with $n$ vertices, and illustrate example of 
  conjectured differences, via drawings, of $\nu$(K$_{8}$) and $\bar{\nu}$(K$_{8}$).  
  They composed Table~\ref{table:hh63} of conjectured values for $\nu$(K$_{n}$)
  and $\bar{\nu}$(K$_{n}$).  It is included here as an interesting historical fact
  and as a reflection on the slow advances in the crossing number problem. 
  Table~\ref{table:hh63} as related to  $\nu$(K$_{n}$) has seen no modification 
  since its inception.  For the current status of $\bar{\nu}$(K$_{n}$) see Section~\ref{sec:ocn}.
    
\begin{table}[h]
	\centering
		\begin{tabular}{|c|ccccccccc|} \hline
		$n$ 										& 2 & 3 & 4 & 5 & 6 & 7 &  8 &  9 & 10 \\ \hline
		$\nu$(K$_{n}$)					& 0 & 0 & 0 & 1 & 3 & 9 & 18 & 36 & 60 \\	\hline 
		$\bar{\nu}$(K$_{n}$)	  & 0 & 0 & 0 & 1 & 3 & 9 & 19 & 36 & 63 \\ \hline
		\end{tabular}
	\caption{Conjectured Crossing Numbers in 1963}
	\label{table:hh63}
\end{table}

In the same discussion, Conjecture~\ref{cj:cr<rcr} was proposed.

	\begin{conjecture}\label{cj:cr<rcr}[Harary and Hill]
	For complete graphs, the rectilinear crossing number, $\bar{\nu}$(K$_{n}$), 
	exceeds the crossing number, $\nu$(K$_{n}$), for n = 8 and all $n\geq10$.
	\end{conjecture}
	
	In 1971, Singer~\cite{Sin71:rcnocg} verified Harary and Hill's conjecture that
	$\nu$(K$_{n}$)$\neq$$\bar{\nu}$(K$_{n}$) for $n$=8 and $n$=10.  He proved that
	$\bar{\nu}$(K$_{8}$)=19 and $60<\bar{\nu}(K_{10})<63$.
  
  Guy supplied us with Theorem~\ref{th:g72} in 1972.  The reader
	is encouraged to refer to ~\cite{Guy72:cng} for proofs establishing equality of
	Theorem~\ref{th:Kn} for $n\leq10$.  
	
	\begin{theorem}\label{th:g72}[Guy]
	For the complete graph K$_{n}$, for $n\leq10$, it is the case that 
\begin{center}
  $\nu$(K$_{n}$)$= \frac{1}{4}\left\lfloor \frac{n}{2}\right\rfloor\left\lfloor \frac{n-1}{2}\right\rfloor
  \left\lfloor \frac{n-2}{2}\right\rfloor\left\lfloor \frac{n-3}{2}\right\rfloor$.
\end{center}
	\end{theorem}
   
  In addition to proofs for $n\leq10$,~\cite{Guy72:cng} and~\cite{Egg73:cng} supply us 
  with a plethora of 
  information, some of which we briefly describe now.  The introduction of the
  responsibility argument, which is later used~\cite{bdg00:trcnok10i62} in a 
  proof that $\bar{\nu}$(K$_{10}$)=62, is presented.  The responsibility of a vertex
  is defined as the total number of crossings on all edges incident to that vertex.
  Theorem~\ref{th:parity} from~\cite{Egg73:cng,Guy72:cng} gives us information on the parity of K$_{n}$.
 
  \begin{theorem}\label{th:parity}[Guy,Eggleton]
	The parity of the number of crossings in all good drawings of K$_{n}$ is the same,
	for {\it n} odd.  
		
	\end{theorem}
	
	and crossing number subdrawing information:
	
	 \begin{theorem}\label{th:subKn-1}[Guy]
	Given any drawing of K$_{n}$ with $c$ crossings, there exists at least one sub-drawing
	K$_{n-1}$ with at most, and one with at least, $\left\lfloor \frac{n}{n-4}c\right\rfloor$
	crossings.
	\end{theorem}
  
  Guy also conjectured solution to the rectilinear crossing number problem.  See 
  Section~\ref{sec:ocn} for details.
   
  Eggleton~\cite{Egg73:cng} and Harbo et al.~\cite{hg90:nndsg} supply work on generating all 
  nonequivalent complete graphs for $n\leq6$ as well as for some other graph families.
       
  Garey and Johnson helped explain why advancement in solving the
  crossing number problem was so trying.  They proved the crossing number problem to be
  NP-complete~\cite{gj83:cninpc} as Theorem~\ref{th:npc} states.
  
  \begin{theorem}\label{th:npc}[Garey and Johnson]
	Given a graph G and an integer K, the question of if ${\nu}$(G)$\leq$K is NP-complete.  
	\end{theorem}
	
	After this discovery, much research turned away from the crossing number problem to
	other related problems though it was not abandoned completely.  Research mainly 
	focused on lower bound tightening and the quest
	for exact values fell off .  For the reader interested in NP-completeness, refer
	to~\cite{gj79:npc}.  The rectilinear crossing number problem has been found to be
	NP-hard~\cite{bien91:sphcnp}.  Pach and Toth~\cite{pt00:tpocn} show that the odd crossing
	number problem is NP-complete and that of the pairwise crossing number is NP-hard.
  
  Harris and Harris~\cite{hh96:apafctmcnoag} proposed an exhaustive search algorithm
  for calculating the crossing number of a graph.  This algorithm was implemented in
  parallel by Tadjiev and Harris~\cite{Tadj98:pcgvmcng,th97:pcmcng}.  The test family
  of graphs was the complete graph family.  Proposed improvements, a dynamic work queue
  and graph theoretic reductions of the search space, became evident from this initial
  parallel implementation.  The algorithm shall be explained in more detail in 
  Section~\ref{sec:es} as it is the algorithm from which this dissertation grew.   
  
  While there are a few infinite classes of graphs for which tight bounds are
  known~\cite{bd93:brcn,LIEB01:pgasaab}, we are lacking efficient lower bound methods
  for estimating the crossing number of a variety of graphs.
  
  One of the methods seeing a lot of use in the lower bound search is the Bisection method.
  It has proven to be one of the most powerful.
  In Leighton's article~\cite{lei84:nlbtvlsi} discussing the use of the crossing number
  to estimate the required chip area for VLSI circuit layout of graph he proved a
  general lower bound for $\nu$(K$_{n}$) using the relationship of the crossing number
  to bisection width.
  This lower bound was also found independently by Ajtai et al.~\cite{acns82:cfs}.
  Many extensions of this lower bound have been 
  discovered~\cite{lei83:civlsi,lei84:nlbtvlsi,pss96:acn,sv97:vlsilstrn}.  The best combines
  Leighton's with the constant 1/33.75 by Pach et al.~\cite{pst99:nbocn} giving 
  us Theorem~\ref{th:cnlb}.
  
  \begin{theorem}\label{th:cnlb}[Leighton,Ajtai et al., Path et al.]
	Let G be a graph with $n$ vertices and $e$ edges with $e\geq7.5n$.
  \begin{center}
  $\nu(G)\geq\frac{1}{33.75}\frac{e^3}{n^2}$.
  \end{center}
	\end{theorem}
	
	 A similar inequality holds for the odd crossing number, see~\cite{pt00:tpocn}, with
  a crossing constant of 1/64.
  
  Another technique, using the cutwidth of a graph was spawned from this extension 
  of Leighton's lower bound.  
  An improvement of that bound was discovered~\cite{dv03:cnac} by replacing the
  bisection width with the cutwidth of the graph. In using the cutwidth of a graph
  they were also able to find an upper bound on path-width of G in terms of its
  crossing number. 
  
  Pach et al.~\cite{pst99:nbocn} prove the conjecture by Erd\"{o}s and Guy~\cite{eg73:cnp}
  that {\it K}(n,e)n$^2$/e$^3$ tends to a positive constant as n approaches infinity and
  n $<<$ e $<<$ n$^2$ to give us Theorem~\ref{th:pteg}.  {\it K}(n,e) is defined
  to be the minimum of $\nu$(G) taken over all graphs with n vertices and at least e edges.
  
  \begin{theorem}\label{th:pteg}[Pach et al.]
  Given a graph G, with $n$ vertices and at least $e$ edges, if  $n<<e<<n^2$,
    \[\lim_{n\rightarrow\infty}{\it K}(n,e)\frac{n^2}{e^3}=C>0\]
  where {\it K}(n,e) is the minimum of $\nu$(G) taken over all graphs with $n$ 
  vertices and at least $e$ edges.
	\end{theorem}
	
    They also reported on some new 
  bounds for graphs with monotone properties, specifically given a graph G with 
  n vertices, $e \geq 4n$ edges without a cycle of length 4 (6), then its crossing 
  number is at least ce$^4$/n$^3$ (ce$^5$/n$^4$) where $c > 0$ is a suitable constant.
  The bisection width, crossing number relationship~\cite{lei83:civlsi} aided in
  these results.
   
  
  In the search for an improved lower bound for $\nu(K_{7,n})$, de Klerk et 
  al.~\cite{kmprs:ibcnkmnkn}, using quadratic optimization techniques, have
  discovered improved bounds for K$_{n}$.  
  They present their results in terms of asymptotic ratios as follows.  
  Let $G(K_{n}$) be the conjectured crossing number
  for the complete graph of order $n$ as stated in Conjecture~\ref{cj:Kn}, then
    \[\lim_{n\rightarrow\infty}\frac{{\nu} (K_{n})}{G(K_{n})}\geq0.83\]
  Asymptotic ratios are an eloquent way to appreciate how close research is to Guy's conjectured
  result.  The limit above, call it $C$, was described and shown to exist~\cite{rt97:rbcnccbg} 
  along with $A$ and $B$ as follows 
  \[A = \lim_{n\rightarrow\infty}\frac{{\nu} (K_{m,n})}{Z(K_{m,n})}\
  \:, and \:\:\:\:\:\:
  B = \lim_{n\rightarrow\infty}\frac{{\nu} (K_{n,n})}{Z(K_{n,n})}\]
  where Z(K$_{m,n}$) is Zarankiewicz's Conjecture~\ref{cj:Z} and
  it is shown that $C \geq B$.  These results allowed de Klerk et al. to 
  arrive at their new lower bound for $\nu (K_{n})$ as an extension of the following 
  bipartite lower bounds they found, also reported as asymptotic ratios
  \[\lim_{n\rightarrow\infty}\frac{{\nu} (K_{m,n})}{Z(K_{m,n})}\geq 0.83\frac{m}{m-1}\ 
  \:, and \:\:\:\:\:\:   
   \lim_{n\rightarrow\infty}\frac{{\nu} (K_{n,n})}{Z(K_{n,n})}\geq 0.83\]
 Richter and Thomassen~\cite{rt97:rbcnccbg} have a good overview of $\nu (K_{n})$ and
 $\nu (K_{m,m})$ in addition to the above mentioned asymptotic ratios.
    	   
  Grohe has recently shown~\cite{Groh02:ccnqt} that the crossing number problem is 
  fixed parameter tractable. 
  	\begin{definition}\label{def:fpt}
		A problem is fixed parameter-tractable if there is a constant $c \geq  1$ such that
  for every fixed $k$ the problem can be solved in time $O(n^c)$.
	\end{definition}
  
  He showed that for every fixed $k$ there is a quadratic time
  algorithm that decides if a graph G has crossing number at most $k$.  This result
  has only theoretical interest as the run time is $\mathcal{O}(f(k)n^2)$ where $f$ is at least
  doubly exponential.  Yet, as Grohe states, knowing that the crossing number problem is 
  fixed parameter-tractable may help researchers find algorithms that have practical
  application for small values of $k$.   
  
  For a fairly complete and up to date list of papers related to crossing numbers 
  see~\cite{Vrto:cngb}. ~\cite{LIEB01:pgasaab} has a nice section on crossing 
  numbers along with several
  references to crossing number work related to the hypercube of dimension $n$, Cartesian
  product graphs and others.  Section~\ref{sec:ocn} mentions other crossing
  number references.
  Additionally, Path and Toth~\cite{pt00:tpocn} discuss several problems on crossing 
  numbers.  Their paper includes several open questions along with a list of references.
  } % end \subsection{The Crossing Number of Graphs}
 
 
 %\newpage
 
  
 \subsection{Rectilinear and Other Crossing Numbers}\label{sec:ocn}
 {
 
 	The crossing number is the minimum number of crossings with which it is possible to 
 	draw graph $G$ in the plane. 	The result is the same whether G is drawn in the plane or 
 	on the surface of a sphere.  This is not the same number obtained by drawing
 	G on a sphere with the edges as arc of great circles, or the rectilinear crossing
 	number~\cite{hh63:noccg}.  Rectilinear crossing numbers have seem extensively more 
 	research than crossing numbers.   Rectilinear research restricts edges to 
 	geodesics, i.e. straight lines in the plane, or to great circle arcs on the sphere.
 	It has a geometric nature that can be exploited, the convex hull, making it more 
 	accessible to researchers hoping to find exact values then the standard crossing number.
 
 Guy conjectured that an upper bound for the rectilinear crossing number, 
  Theorem~\ref{th:recKn}, presented
  in~\cite{Egg73:cng,Jen71:ubrcncg} was an equality.  The conjecture has been disproven,
  see ~\cite{ak01b:tpsotdbacoaar,bdg00:trcnok10i62,Sin71:rcnocg,th96:psoafmrmcp}, but the
  upper bound still stands.       
  
  \begin{theorem}\label{th:recKn}[Guy]
	The rectilinear crossing number of the complete graph satisfies the inequality
		
\begin{center}
  $\bar{\nu}$(K$_{n}$)$\leq \lfloor \frac{(7n^{4} - 56n^{3} +
                128n^{2} + 48n \lfloor \frac{(n-7)}{3}\rfloor + 108)}
                {432} \rfloor $.
\end{center}
	\end{theorem}
	
 	The search for the exact value of the rectilinear crossing number 
	problem has seen great advancement recently.  Interestingly enough it was
	accomplished via exhaustive search techniques.
	The exact values of $\bar{\nu}$(K$_{n}$) for $n\leq9$ has been known for some
	time~\cite{eg73:cnp}. That $\bar{\nu}$(K$_{10}$)=61 or 62 was found by Singer in
	1971 in an unpublished manuscript~\cite{Sin71:rcnocg}.  This long standing 
	question was answered,$\bar{\nu}$(K$_{10}$)=62, by an intricate combinatorial proof 
	presented by Brodsky et	al.~\cite{bdg00:trcnok10i62}, in 2000.  This result was 
	confirmed by Aichholzer et al.~\cite{ak01b:tpsotdbacoaar} via exhaustive enumeration of all
	combinatorially inequivalent set of points (order types). See~\cite{aak02:porcn,ak05:eotfspswa}
	for a description of this enumeration method.  Aichholzer et 
	al.~\cite{ak01:aoteanrotrcn,aak02:porcn} have determined $\bar{\nu}$(K$_{n}$) 
	for up to {\it n} = 17.  Table~\ref{table:rcn} illustrates
	the rectilinear crossing number results to date.
	        
  \begin{table}[h]
	\centering
		\begin{tabular}{|c|cccccccccccccccc|} \hline
	$n$ 								 & 2 & 3 & 4 & 5 & 6 & 7 &  8 &  9 & 10 &  11 &  12 &  13 &  14 &  15 &  16 &  17 \\ \hline		   $\bar{\nu}$(K$_{n}$) & 0 & 0 & 0 & 1 & 3 & 9 & 19 & 36 & 62 & 102 & 153 & 229 & 324 & 447 & 603 & 798 \\ \hline
		\end{tabular}
	\caption{Rectilinear Crossing Number up to $n$ = 17}
	\label{table:rcn}
\end{table}
 
  Guy et al. introduced the idea of the toroidal crossing number~\cite{gjs68:tcnotcg}
  $cr_{1}(K_{n})$ with some preliminary results for $n\leq10$.  The examination of
  the torus was a step toward looking at crossing numbers on orientable surfaces
  of higher genus.  They also make a reference (unpublished) to Ringel as introducing
  the idea of a local crossing number.
  
   Path and Toth define pairwise crossing number, odd crossing number and examine 
   the relationship of them with the crossing number~\cite{pt00:tpocn,pt00b:wcniia} and
   ask if it is true that, for every graph G
   
\begin{center}
 ODD-CR(G) = PAIR-CR(G)=CR(G).
\end{center}
 
 Just recently, Pelsmajer et al.~\cite{pss05:ocnncn} claim to have shown that
 ODD-CR(G)$\neq$CR(G) using weighted maps on the annulus.  An annulus is a disk
 with a hole in the center.
 
 
 Conjecture~\ref{cj:Z} has been verified for min(m,n) $\leq  6$ by Kleitman~\cite{Klei70:cnk5n}
 and also by    Woodall~\cite{Wood93:cogzcnc}
 for the cases $7 \leq m \leq 8$ and $7 \leq n \leq 10$.   It is unknown for all other
 values.  For discussion on the best
 known lower bounds for differing cases of $\nu$(K$_{m,n}$) see~\cite{kmprs:ibcnkmnkn}.  These
 bounds were achieved using combinatorics in conjunction with quadratic optimization techniques.  
 Shahrokhi et al.~\cite{sssv00:nlbbcnwa} looked at a lower bound argument for bipartite graphs based on 
 Menger's Theorem which 
 relates the bipartite crossing number of a graph to the edge connectivity properties
 of the graph.  It is interesting to note that they also make use of spectral graph 
 theory.  
 
 
 One graph family where there has been success in finding exact values is the Cartesian
 products of
 cycles $C_{m} \times C_{n}$.  Glebsky and Salazar~\cite{gs:cncmcnc} have proven the long
 standing conjecture that $\nu(C_{m} \times C_{n}) = (m-2)n$ for all 
 $m, n$ such that $n \geq m \geq 3$ is true for all but finitely many $n$, for each m.  
  
 } % end \section{Other Crossing numbers}
 
 %\newpage
 
  
 \subsection{Graph Isomorphism}\label{sec:gi}
 {
 	An overview of the state of the graph isomorphism problem through 1996
  is presented in ~\cite{fort96:gip}.
  Solving the graph isomorphism problem is generally done using one of two distinct
  approaches.  Both usually involve one or many vertex invariants to improve 
  efficiency.  The first approach finds isomorphism between two given graphs by
  directly finding the mapping between their vertices.  The technique can employ
  approximation or exact methods.  This brute force graph matching has applications
  in several contexts related to computer vision and pattern recognition contexts.
    
  The second approach involves canonical labeling of the graphs in question.  A function
  that produces a canonical label C(G) for a given graph G is defined.  Canonical 
  labeling works due to the fact that C(G) = C(H) if and only if graph G and H are isomorphic.  
  The most widely used canonical labeling algorithm is nauty~\cite{m81:pgi}.  
  
  Nauty, standing for "`No AUTomorphisms, Yes?", is considered to be one of the most
  powerful and practical methods available for solving graph isomorphism problems
  and is labeled by many as the ``world's fastest isomorphism testing program".  Refer
  to Section~\ref{sec:ifkn} for an overview of Nauty's application to this dissertation.     
 
 } % end \subsection{Graph Isomorphism}
 
 \section{Exhaustive Search Algorithm}\label{sec:es}
 {
 	\hspace{1em}
	As noted, we employ an exhaustive-search branch-and-bound
	algorithm proposed by \cite{hh96:apafctmcnoag}.  An overview 
	of it is presented
	to allow for understanding of the new work presented
	in Chapter 3.  
	
	\subsection{Edmonds' Rotational Embedding Scheme}\label{sec:eres}

	\hspace{1em}
	We start with a look at the Rotational Embedding Scheme, first
	formally introduced by Edmonds~\cite{edmo60:crps} in 1960 
	and then discussed
	in detail by Youngs~\cite{youn63:migg} a few years later.  The following
	is the formal statement of the Rotational Embedding Scheme as
	presented in~\cite{CHAR96} on pages 196-197.


	\begin{quote}
	Let G be a nontrivial connected graph with $V(G) = \{v_{1},
	v_{2}, \ldots, v_{n}\}$.  For each 2-cell embedding of G on
	a surface there exists a unique n-tuple $(\pi_{1}, \pi_{2},
	\ldots, \pi_{n})$, where for  $i = 1, 2,$ $\ldots, n$, $\pi_{i}
	:  V(i) \rightarrow V(i)$ is a cyclic permutation that describes
	the subscripts of the vertices adjacent to $v_{i}$.  Conversely,
	for each such n-tuple $(\pi_{1}, \pi_{2}, \ldots,  \pi_{n})$,
	there exists a 2-cell embedding of G on some surface such that
	for $i = 1, 2, \ldots,n$ the subscripts adjacent to $v_{i}$ and in
	the counterclockwise order about $v_{i}$, are given by $\pi_{i}$.
	\end{quote}

       	For example, consider Figure~\ref{fig:edmonds} which gives a
        planar embedding of a graph.  From this graph we obtain the
        following counterclockwise permutations associated with each
        vertex:                                                    
               
        \begin{center}
        \begin{tabular}{ll}
                $\pi_{1} = (6, 4, 2)$   & $\pi_{2} = (1, 4, 3)$  \\
                $\pi_{3} = (2, 4)$      & $\pi_{4} = (3, 2, 1, 5)$ \\
                $\pi_{5} = (4, 6)$      & $\pi_{6} = (5, 1)$         
        \end{tabular}                                                
        \end{center}                                        

\begin{figure}[!ht]
       \begin{center}
       		figure house.ps goes here
       		       \vspace*{2in}
         %\includegraphics[width=1.0in]{ch3/unbalanced}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{A Planar Embedding of a Graph}
       \label{fig:edmonds}
 \end{figure}                     
%        \begin{figure}
%	\epsfxsize=2.5in
 %       \centerline{\epsffile{house.ps}}
 %       \caption{A Planar embedding of a graph}          
 %       \label{fig:edmonds}                              
 %       \end{figure}                           
                           
        From these permutations we can obtain the edges of the graph
        and the number of regions of the graph.  For instance, this 
        graph has 4 regions.  The edges for one of these regions can be
        traced as follows:                                             
	{                                                                      
                \newcounter{bean}
                \begin{list}{\arabic{bean})}{\usecounter{bean}
                        \setlength{\rightmargin}{\leftmargin} 
                        \parsep=0pt\itemsep=0pt\topsep=0pt}   
                \item Start with edge (1,2)                  
                \item Go to permutation $\pi_{2}$ and find out who
			follows
                        1, and it is 4.  Therefore the second edge
                        is (2,4).

                \item Go to permutation $\pi_{4}$ and find out who
			follows 2,
                        and it is 1.  Therefore the third edge is (4,1).
   
               \item Go to permutation $\pi_{1}$ and find out who
			follows 4  
                        and it is 2.  This yields edge (1,2) which
                        was the original edge so we are finished.
                \end{list}                                        
        }                                                        
        \noindent         
        The region we looked at was bounded by the edges (1,2), (2,4),
        and (4,1).  The other regions and edges can be found in a
        similar manner.
        
        The important thing to note at this point is the converse
        portion of the Rotational Embedding Scheme: every collection of
        vertex permutations corresponds to an embedding on some surface.
        Given a set of permutations, we can trace the edges and determine
        the genus of the surface.


    \subsection{The Exhaustive Search Algorithm}

	\hspace{1em}
	
	The algorithm presented in~\cite{hh96:apafctmcnoag} maps the solution 
	space of the crossing number
	problem onto a tree.  The tree is then searched for the 
	crossing number with a branch and bound depth first search
	(DFS). A DFS searches more deeply into the tree for a solution
	whenever possible.  Once a path is found from the root to a leaf
	representing a solution, the search backtracks to explore the
	nearest unsearched portion of the tree.  This continues until
	the entire tree has been traversed.    Branch and bound allows us
	to change one small part of the DFS algorithm.	When the cost to
	get to a vertex $v$ exceeds the current optimal solution, we tell
	the DFS algorithm not to traverse the subtree having vertex $v$ as
	its root.  This saves us from having to cover a section of the
	search space that is guaranteed to cost more than the current
	optimal solution.

	First we begin with the vertex set for the graph in question
	and begin to add edges.  After each edge is added we determine
	whether the partial graph is still planar.  This is done using
	the Rotational Embedding Scheme.  Once we cannot add any edges
	and keep the partial graph planar we are ready to begin our
	mapping to the tree.

	At this stage our partial graph is the root of our tree.
	The first option we have is the many different ways to draw
	this graph.  The root of the tree has a branch for each possible
	planar embedding.  Now we select the first embedding and begin
	to build the rest of its tree.	We do this by considering laying
	down the next edge (which will go from vertex $i$ to vertex $j$).
	The first option we have is which one of the $k$ regions that
	vertex $i$ is adjacent to should this edge leave through.  These
	regions represent the next layer of our tree.  Once the region
	is selected, the next option is which of the $l$ edges of that
	region the edge will cross.  When we have made this decision,
	we will create a cross vertex (degree 4) and place an edge from
	vertex $i$ to the cross vertex and then try to lay the edge from
	the cross vertex to vertex $j$.  This may be possible directly,
	or it may require more cross vertices.

	We lay down the remaining edges in a similar
	manner, and when we have finally laid them all down we have
	reached a leaf in the tree.  At this point we have a cost for
	the current solution which is the number of cross vertices we
	have added.  This number of crossings becomes the new bound. The
	DFS continues by backing up and trying other decisions in the
	tree using the bound as a stopping criteria.  We proceed until the
	entire solution space is traversed.  In order to understand this,
	let us walk through the algorithm with $K_{5}$ as our example. In
	Figure~\ref{fig:k5b} we have the vertex set for the graph with
	all the edges added to the graph while it can still remain planar.


\begin{figure}[!ht]
       \begin{center}
       		K5a.ps here
       		       \vspace*{2in}
         %\includegraphics[width=1.0in]{ch3/unbalanced}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Planar Portion of $K_{5}$}
       \label{fig:k5b}
 \end{figure}
 
%	\begin{figure}
%	\epsfxsize=2.5in
%        \centerline{\epsffile{K5a.ps}}
%	\caption{Planar portion of $K_{5}$}
%	\label{fig:k5b}
%	\end{figure}

	At this stage the algorithm states that we are to take
	all remaining edges and try to lay them down one at a time.
	This is fairly simple in this case since there is only one
	edge left to be added and that is from vertex $i$ to vertex $j$.
	Now we have three choices, and these are the three regions that
	vertex $i$ is adjacent to (R1, R2, and R3).  We select R1 which
	has 3 edges and find that we cannot legally cross 2 of the edges
	(since they are incident with $i$) so there is only one choice. We
	then place a cross vertex on this edge and connect an edge from $i$
	to the cross vertex as shown in Figure~\ref{fig:k5c}.  We then find
	out if we can draw the edge from the cross vertex to $j$ and keep
	the graph planar.  In this case we can and we are finished with
	this edge and have one crossing. This solution is shown in 
	Figure~\ref{fig:k5d}.  The algorithm then backtracks and tries the other
	regions $i$ is adjacent to and finds out that there are multiple
	ways to draw $K_{5}$ with one or fewer crossings.

\begin{figure}[!ht]
       \begin{center}
       		K5b.ps here
       		       \vspace*{2in}
         %\includegraphics[width=1.0in]{ch3/unbalanced}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Beginning to Lay Down an Edge for $K_{5}$
       \label{fig:k5c}
 \end{figure}
 
%	\begin{figure}
%	\epsfxsize=2.5in
%        \centerline{\epsffile{K5b.ps}}
%	\caption{Beginning to lay down an edge for $K_{5}$}
%	\label{fig:k5c}
%	\end{figure}


\begin{figure}[!ht]
       \begin{center}
       		K5c.ps here
       		       \vspace*{2in}
         %\includegraphics[width=1.0in]{ch3/unbalanced}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{One drawing of $K_{5}$ with one crossing}
       \label{fig:k5d}
 \end{figure}
%	\begin{figure}
%	\epsfxsize=2.5in
 %       \centerline{\epsffile{K5c.ps}}
%	\caption{One drawing of $K_{5}$  with one crossing}
%	\label{fig:k5d}
%	\end{figure}
  
 } % end \section{Exhaustive Search Algorithm}
 
 
 
 
 
 \newpage
 
 
 
 
 
 	
 	