\chapter{Background}\label{chap2}
 
 In this chapter the basic definitions needed for reading this dissertation are presented.  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, as it relates to this work,
 is given in Section~\ref{sec:gi}.  Finally, Section~\ref{sec:es} describes in detail the
 exhaustive search algorithm from which this new research initiated. This background allows for
 clear understanding as progress is made toward 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 objects 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}.  This more convenient notation is used when possible.  
 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, it 
 is said that $e_{1}$ and $e_{2}$ are {\it 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}


In figure~\ref{fig:graph} the above terms are illustrated for two graphs.
The graph in (a) has order $n = 4$ and size
$m = 4$.  Vertices 1 and 2 each have degree 2, vertex 3 has degree 3, and vertex 4 has
degree 1.  Graph (b) has order $n = 5$, size $m = 10$, and all five vertices have degree
4.
\begin{figure}[!ht]
       \begin{center}
       	\includegraphics[width=4.0in]{ch2/GraphDescribed.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Example Graphs}
       \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 in Figure~\ref{fig:iso}(a) and (b) are isomorphic, but graph (c) is not
 isomorphic to either (a) or (b).
 \begin{figure}[!ht]
       \begin{center}
       	\includegraphics[width=4.5in]{ch2/IsoAndNotChap2.pdf}
         % [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 \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}, graph (a) is a complete graph of order six.  Graph (b)
 is a complete graph of order 5, and graph (c) is not complete.  Graphs (b) and (c) are both subgraphs
 of graph (a).
 
 \begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=5.0in]{ch2/SubgraphsChap2.pdf}
         % [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 \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} consisting of two partite sets of order $m$ and $n$
  is denoted K($n$,$m$) or K$_{{\it n,m}}$.  The graph K$_{1,n}$ is called a {\it star}.
  
  
  A complete bipartite graph illustrating Tur\'{a}n's brick factory problem is seen in 
  Figure~\ref{fig:bipart}.  To visualize the brick factory layout, let vertices
  1 and 2 represent the brick ovens (one partite set), vertices 3, 4, and 5 
  represent the storage areas (the second partite set), and
  the edges of the graph represent the rails connecting all ovens to all storage locations.
  
  \begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=2.5in]{ch2/bipartiteChap2.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{A Bipartite Graph}
       \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_{1}\in$ E(G).  
  \end{definition}
  
   \begin{definition}\label{def:walk}
  A \textbf{u-v walk} of graph G is a finite, alternating sequence
  	\center
  	$u=u_{0},e_{1},u_{1},e_{2}...,u_{k-1},e_{k},u_{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$ {\it 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 that 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.  Bisection width is denoted bw(G). 
  \end{definition}

	Figure~\ref{fig:biwidth} shows a graph with the dashed lines indicating the 
	edges that need to be
	deleted to disconnect it into two equal-sized pieces.  
	The bisection width of the graph is 3.
	 
 \begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=2.5in]{ch2/bisectionWidthChap2.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{The Bisection Width of a Graph}
       \label{fig:biwidth}
 \end{figure}
 
 
  \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 cutwidth problem is one of arranging vertices in a line so that the maximum number
  of edges crossing the $i$th place, for all $i$, is minimized.  The illustrations in 
  Figure~\ref{fig:cutwidth} aid in understanding the cutwidth definition.
  Graph (a) is shown as a linear embedding in (b).  The horizontal dashed line crosses
  the region between vertices 2 and 4 three times, so the region between 2 and 4
  has a cut of 3 indicated by the three edges intersected.  The cutwidth of the graph 
  is the minimum of all possible maximum cuts
  over all possible linear embeddings.  The cutwidth of graph (a) is three.    
 
 \begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=4.0in]{ch2/CutwidthChap2.pdf}
         % [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.  
    
  \begin{definition}\label{def:plane}
  A planar graph that is embedded in the plane is called a \textbf{plane} graph.  
  \end{definition}
 
 Figure~\ref{fig:plane} graph (a) is a planar graph, though as drawn it is not plane.
 The illustration in (b) is its plane representation. 
  
 \begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=4.0in]{ch2/PlanarAndPlaneChap2.pdf}
         % [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}
  
  The regions of G can be thought of 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 that $x$ can be joined 
  to a point of R by a curve, all of whose points that differ from $x$ belong to $R$.  
  \end{definition}
  
  For illustration, Figure~\ref{fig:regbound} shows the regions of K$_{4}$ along with
  their boundaries.  Region R1 is bounded by vertex 1, edge (1,2), vertex 2, edge
  (2,4), vertex 4 and edge (4,1).  The other region boundaries can be determined
  similarly.  Notice
  that there is an exterior region, R4. It is bounded by vertex 1, edge (1,3), 
  vertex 3, edge (3,2), vertex 2, and edge (2,1).  For the discussion in this dissertation
  it is said that a vertex or edge on the boundary of a region is adjacent to that region. 
  
 \begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=2.5in]{ch2/K4chap2.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{The Regions of K$_{4}$ and Their Boundaries}
       \label{fig:regbound}
 \end{figure}
  
  The order, size, and number of regions of any connected plane graph are related by
  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 for discussion of the number of regions of a connected planar graph. 
  
  Nonplanar graphs cannot be drawn in the plane; some edges must cross. This leads 
  to the definition of the crossing number of a graph, a standard measure of graph nonplanarity,
  as well as to the definition of a good drawing.
  
  \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} 
  
  \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, and 
  	\item no edge passes through a vertex of the graph G.
  \end{itemize}
  \end{definition}  

Figure~\ref{fig:good} illustrates the four edge relationships listed in
Definition~\ref{def:good drawing} that are not allowed in good graph drawings.

\begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=3.0in]{ch2/NoGoodchap2.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Illegal Edges for a Good 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} 
  
  F\'{a}ry~\cite{fary48:slrpg} is known 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$.
  
  The following definitions are relevant to the discussion in Section~\ref{sec:eres} of
  Edmonds' Rotational Embedding Scheme.  A compact orientable 2-manifold is a surface 
  that can be thought 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. The 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.  This dissertation is concerned only with
  graphs of genus 0. 
  
    \begin{definition}\label{def:2-cell}
  A region of a graph G is \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 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-cell, the embedding is called
  a \textbf{2-cell embedding}. 
  \end{definition} 
    
  {\it Via} an extension of Euler's Formula (Theorem~\ref{thm:Euler}), it is noted that every  
  embedding of a connected graph G on a surface of genus gen(G) results 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, 
 so difficult to attack in general, has followed many splintered paths as 
 individuals have attempted to make progress on the problem 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.  An overview of the crossing number of complete graphs is presented 
 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.
 Section~\ref{sec:gi} concludes with an overview of graph 
 isomorphism as it relates to this body of work.  
 
 
\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} points out an error in Zarankiewicz's proof that was discovered in 1965 by
  Kainen and Ringel and shared with Guy {\it via} private communication.  The error was the assumption
  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 K$_{m,n}$ 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 K$_{m,n}$ 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}.  Guy mentioned that Erd\"{o}s had been looking
  at the problem for at least twenty years prior.  No improved upper bound
  has been published to date.
 
  \begin{theorem}\label{th:Kn}[Guy]
	The crossing number of the complete graph K$_{n}$ 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 is 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).  
	The inductive step from even to odd cannot be made.  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 1960s, 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 K$_{n}$ 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 examples of 
  conjectured differences {\it 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 a 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, by Harary and Hill, 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{Egg73:cng} and~\cite{Guy72:cng} supply a plethora of 
  information, some of which is briefly described 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 {\it 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} supplies information on the parity 
  of K$_{n}$, and Theorem~\ref{th:subKn-1} addresses the crossing number of sub-drawings.
 
  \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}
	
		
	 \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 a 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, although 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  the pairwise crossing number problem 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.  Needed improvements, a dynamic work queue
  and graph theoretic reductions of the search space, became evident from this initial
  parallel implementation.  This algorithm is explained in more detail in 
  Section~\ref{sec:es} since 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}, efficient lower bound methods
  for estimating the crossing number of a variety of graphs are lacking.
  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 between the crossing number
  and the bisection width.
  This lower bound was also found independently by Ajtai {\it et al.}~\cite{acns82:cfs}.
  Many extensions of this lower bound have been 
  discovered~\cite{lei83,lei84:nlbtvlsi,pss96:acn,sv97:vlsilstrn}.  The best of these bounds combines
  Leighton's bound with the constant $\frac{1}{33.75}$ by Pach {\it et al.}~\cite{pst99:nbocn}, producing
  Theorem~\ref{th:cnlb}.
  
  \begin{theorem}\label{th:cnlb}[Leighton, Ajtai et al., Pach et al.]
	Let G be a graph with $n$ vertices and $e$ edges with $e\geq7.5n$.  Then
  \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 $\frac{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,
  Djidjev and Vrt'o were also able to find an upper bound on pathwidth of G in terms of its
  crossing number. 
  
  Pach {\it et al.}~\cite{pst99:nbocn} prove the conjecture by Erd\"{o}s and Guy~\cite{eg73:cnp}
  that ${\it K}(n,e)\frac{n^2}{e^3}$ tends to a positive constant as $n$ approaches infinity and
  $n$ $<<$ $e$ $<<$ $n^2$ to produce 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, then its crossing 
  number is at least $\frac{ce^4}{n^3}$  where $c > 0$ is a suitable constant.
  A graph without a cycle of length 6 results in a crossing number of at 
  least $\frac{ce^5}{n^4}$. 
  The bisection width and crossing number~\cite{lei83} aided in these results.
   
  
  In the search for an improved lower bound for $\nu(K_{7,n})$, de Klerk {\it et 
  al.}~\cite{kmprs:ibcnkmnkn}, using quadratic optimization techniques,
  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 {\it 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 ${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}. Liebers' work~\cite{LIEB01:pgasaab} has a 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, Pach 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 arcs of great circles, the rectilinear crossing
 	number~\cite{hh63:noccg}.  Rectilinear research restricts edges to 
 	geodesics, {\it i.e.} straight lines in the plane or to great circle arcs on the sphere.
 	The rectilinear problem has a geometric nature that can be exploited, the convex hull, making it more 
 	accessible than the standard crossing number to researchers hoping to find exact values.
 	For this reason, rectilinear crossing numbers have seen extensively more 
 	research than crossing numbers.   
 
 Guy conjectured that the upper bound for the rectilinear crossing number, given in 
  Theorem~\ref{th:recKn}, and 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 K$_{n}$ 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 advancement recently.  These advances were
	accomplished {\it via} exhaustive search techniques.
	The exact value 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 {\it et	al.}~\cite{bdg00:trcnok10i62}, in 2000.  This result was 
	confirmed by Aichholzer {\it et al.}~\cite{ak01b:tpsotdbacoaar} {\it via} exhaustive enumeration of all
	combinatorially inequivalent sets of points (order types). See~\cite{aak02:porcn,ak05:eotfspswa}
	for a description of this enumeration method.  Aichholzer {\it 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 Numbers up to $n$ = 17}
	\label{table:rcn}
\end{table}
 
  Guy {\it et al.}~\cite{gjs68:tcnotcg} introduced the idea of the toroidal crossing number, 
  $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.
  
   Pach and Toth~\cite{pt00:tpocn,pt00b:wcniia} define pairwise crossing number, pair-cr(G), 
   and odd crossing number, odd-cr(G), and examine the relationship between them and the crossing 
   number and ask if it is true that, for every graph G
   
\begin{center}
 {\it odd-cr(G) = pair-cr(G) = $\nu$(G)}.
\end{center}
 
 Just recently, Pelsmajer {\it et al.}~\cite{pss05:ocnncn} claim to have shown that
 $odd-cr(G) \neq \nu(G)$ using weighted maps on the annulus, a disk
 with a hole in the center.
 
 
 Conjecture~\ref{cj:Z} for the crossing number of K$_{m,n}$ 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 {\it 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.  They also make use of spectral graph theory.  
 
 
 One graph family for which 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 for all but 
 finitely many $n$, and for each $m$ 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$.  
  
 } % 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 graphs G and H are isomorphic.  
  The most widely used canonical labeling algorithm is {\it nauty}~\cite{m81:pgi}.  
  
  {\it 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 has been labeled as the ``world's fastest isomorphism testing program''~\cite{m81:pgi}.  
  Refer to Section~\ref{sec:ifkn} for an overview of {\it nauty}'s application to this dissertation.     
 
 } % end \subsection{Graph Isomorphism}
 
 \section{Exhaustive Search Algorithm}\label{sec:es}
 {
 	\hspace{1em}
	As noted, this research originated with 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.  This algorithm makes use of Edmonds' Rotation Embedding Scheme, so
	discussion of that approach begins the review.  
	
	\subsection{Edmonds' Rotational Embedding Scheme}\label{sec:eres}

	\hspace{1em}
	Edmonds' Rotational Embedding Scheme was 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, the
        following are 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}
         \includegraphics[width=3.0in]{ch2/planeEmbedChap2.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{A Planar Embedding of a Graph}
       \label{fig:edmonds}
 \end{figure}                     
                           
        From these permutations the edges of the graph
        and the number of regions of the graph are determined.  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 Refer to permutation $\pi_{2}$ to determine which vertex follows
                        1. It is 4; therefore the second edge is (2,4).

                \item Refer to permutation $\pi_{4}$ to determine which vertex follows 2.
                        It is 1; therefore the third edge is (4,1).
   
               \item Refer to permutation $\pi_{1}$ to determine which vertex follows 4.  
                        It is 2, which corresponds to the original edge (1,2), so the trace is finished.
                \end{list}                                        
        }                                                        
        \noindent         
        The region traced is 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, the edges can be traced and the genus of the surface determined.


    \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 process continues until
	the entire tree has been traversed.  The branch-and-bound approach 
	changes one small part of the DFS algorithm.	When the cost to
	get to a vertex $v$ exceeds the current optimal solution, 
	the DFS algorithm  does not traverse the subtree having vertex $v$ as
	its root.  This modification saves having to cover a section of the
	search space that is guaranteed to cost more than the current
	optimal solution.  The branch-and-bound DFS algorithm is as follows:

	Begin with the vertex set for the graph in question,
	and start to add edges.  After each edge is added, determine, using the Rotational
	Embedding Scheme,
	whether the partial graph is still planar.  Once no more edges can be added
	while keeping the partial graph planar, the mapping to the tree is performed. 

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

	Lay down the remaining edges in a similar
	manner, and, when they are all laid down, a leaf in the tree is reached.  
	At this point a cost for
	the current solution, which is the number of cross vertices, is known.  
	This number of crossings becomes the new bound.  Continue by backing up and trying other branches
	in the
	tree using this bound as a stopping criterion.  Proceed  in this fashion until the
	entire solution space is traversed.  
	
	In order to understand this approach,
	a walk through the algorithm is now presented with $K_{5}$ as an example.
	Figure~\ref{fig:k5b} shows the vertex set for the graph with
	all the edges that can be added to the graph without making it nonplanar.


\begin{figure}[!ht]
       \begin{center}
			 \includegraphics[width=3.0in]{ch2/K5planeChap2}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Planar Portion of $K_{5}$}
       \label{fig:k5b}
 \end{figure}

	At this stage the algorithm states that an attempt be made to take
	all remaining edges and lay them down one at a time.
	This is fairly simple in this case since there is only one
	edge left to be added, the one from vertex $i$ to vertex $j$.  
	Now three choices arise, and these are the three regions to which
	vertex $i$ is adjacent (R1, R2, and R3).  Selecting R1, which
	has 3 edges, leads to the conclusion that there is only one way to lay down 
	edge $ij$ since it cannot legally cross 2 of the edges
	because they are incident with $i$. 
	The algorithm then calls for placing a cross vertex on this edge and connecting an edge from $i$
	to the cross vertex as shown in Figure~\ref{fig:k5c}(a).  The next step is determining
	if the edge from the cross vertex to $j$ can be drawn while keeping
	the graph planar.  In this case it can, and 
	this edge, having one crossing, is complete. This solution is shown in 
	Figure~\ref{fig:k5c}(b).  The algorithm then backtracks and tries the other
	regions to which $i$ is adjacent and finds that there are multiple
	ways to draw $K_{5}$ with one crossing.  This exhaustive search algorithm is the
	foundation for the new work which is presented in Chapter~\ref{chap3}.

\begin{figure}[!ht]
       \begin{center}
			 \includegraphics[width=4.5in]{ch2/K5layEdgeChap2.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Laying Down an Edge for $K_{5}$}
       \label{fig:k5c}
 \end{figure}
  
 } % end \section{Exhaustive Search Algorithm}
 \newpage
 
 
 
 
 
 	
 	