\chapter{Literature Review}\label{ch2}
  
\section{Definitions }\label{sec:def}
{
\newtheorem{definition}{Definition}

Several basic definitions from the field of graph theory were given in Chapter 1. We will now provide the remainder of the definitions necessary for the discussions that follow. Unless otherwise noted, all definitions are derived from~\cite{CHAR96}.
 
\begin{definition}\label{def:order}
The \textbf{order} of a graph is the cardinality of its vertex set, denoted \textbf{n}
\end{definition}

\begin{definition}\label{def:size}
The \textbf{size} of a graph is the cardinality of its edge set, denoted \textbf{m}
\end{definition}

\begin{definition}\label{def:degree}
The \textbf{degree} of a vertex, \textbf{v}, is the number of edges incident with v, denoted \textbf{deg v}. In the case of a complete graph, the degree is n-1 for all vertices. The sum of the degrees of the vertices of a graph is \textbf{2m}.
\end{definition}

\begin{definition}\label{def:matrix}
An \textbf{n x n adjacency matrix} is a representation of a graph of order n in which an entry at position x,y is 1 if the vertices x and y are adjacent, otherwise is 0. Zero entries occur along the main diagonal of the matrix since vertices are not considered to be adjacent to themselves. 
\end{definition}

\begin{definition}\label{def:isomorphic}
Two graphs are \textbf{isomorphic} if there is a one-to-one mapping of their vertex sets that preserves adjacency. Isomorphic graphs therefore have identical adjacency matrices.
\end{definition}

\begin{definition}\label{def:kpartite}
A graph is \textbf{k-partite}, k $\geq 1$, if its vertex set can be partitioned into k subsets called \textbf{partite sets}, such that each element of the edge set of the graph connects a vertex V$_i$ to a vertex V$_j$, $i \neq j$. For k = 2, such graphs are called \textbf{bipartite graphs} (Figure~\ref{fig:bipartite}). A \textbf{complete k-partite graph}, denoted K$_{n1,n2,n3,\ldots,nk}$, is one in which each vertex V$_i$ is connected to every vertex in each of the other partite sets.
\end{definition}

\begin{figure}[!ht]
       \begin{center}
       	\includegraphics[width=4.0in]{ch2/bipartite.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Bipartite Graph}
       \label{fig:bipartite}
 \end{figure} 

\begin{definition}\label{def:planar}
A graph is \textbf{planar} if it can be embedded in the plane (or on the sphere) with no edge crossings apart from those occurring at vertices. If it is embedded in the plane, it is called a \textbf{plane graph}. A graph that cannot be embedded in the plane (because of edge crossings) is referred to as \textbf{drawn} in the plane.
\end{definition}

\begin{definition}\label{def:region}
A \textbf{region} of a plane graph 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 the graph nor lies on any curve corresponding to an edge of the graph. 
\end{definition}

\begin{definition}\label{def:boundary}
The \textbf{boundary} of a region R of a plane graph consists of all points x corresponding to the vertices and edges of the graph 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}

\begin{definition}\label{def:2cell}
A region in an embedding is called a \textbf{2-cell region} if any simple closed curve in that region can be continuously deformed or contracted in that region to a single point.
\end{definition}

\begin{definition}\label{def:2cellembedding}
An embedding is a \textbf{2-cell embedding} if all the regions in the embedding are 2-cell.
\end{definition}


\begin{theorem}\label{thm:Euler}[Euler's Formula]
If a graph, G, is a connected (essentially the same as complete) plane graph with n vertices, m edges and r regions than the following relationship holds:	
  \center
  \textbf{$n - m + r = 2$}
  \endcenter
  \end{theorem}

Proof of Theorem~\ref{thm:Euler} can be found in~\cite{CHAR96}, page 155. A consequence of Theorem~\ref{thm:Euler} is that every two embeddings of a connected planar graph in the plane have the same number of regions.

\begin{definition}\label{def:crossingnum}
The \textbf{crossing number} of a graph, denoted \textbf{cr(G)} or \textbf{$\nu$(G)}, is the minimum number of edge crossings among its drawings in the plane. Per Definition~\ref{def:planar}, such a graph is nonplanar unless its crossing number is 0. (A subset of crossing number problems considers the \textbf{rectilinear crossing number}, which has the added requirement that each edge is a straight line segment~\cite{hh63:noccg}. These graphs will not be considered further here.)
\end{definition}

\begin{definition}\label{def:mingraph}
A \textbf{minimal graph} is one that exhibits the crossing number when drawn in the plane. 
\end{definition}

\begin{definition}\label{def:goodgraph}
A \textbf{good drawing} of a graph, G, is one in which:
 \begin{itemize}
	\item adjacent edges never cross
	\item two nonadjacent edges cross at most once
	\item no edge crosses itself
	\item no more than two edges cross at a point of the plane and
  \item the (open) arc in the plane corresponding to an edge of the graph contains no vertex of the graph
 \end{itemize}
\end{definition}
   
} % end \section{Definitions}
 
\section{History of the Minimal Crossing Number \\Problem}\label{sec:history}
 {
\subsection{Initial Description }\label{sec:id}
 {
 
Credit for the original description of the Crossing Number Problem is generally given to Paul Tur\'{a}n, based on his personal experience in a brick factory near Budapest during World War II~\cite{Guy69}. In the factory were kilns, where bricks were made, and storage yards, where they were stacked. The former were connected to the latter by rail tracks, forming what we now call a complete bipartite graph. Tur\'{a}n noticed that problems often arose at the points where rails crossed, with trains jumping the tracks and bricks falling to the ground. He mused that those problems and the extra work they created could have been minimized had someone thought through the track layout in advance to minimize the number of crossings. Tur\'{a}n subsequently delineated his problem in lectures given in 1952 in Warsaw and Wroclaw, and it became known as Tur\'{a}n's Brick Factory Problem.

In the Warsaw audience was a mathematician named Zarankiewicz, who became one of the first to take up the challenge. In 1954, he conjectured that the crossing number of a complete bipartite graph is as follows~\cite{Zara:ptcg}:
	
\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}	
He noted that his conjecture was concurrently and independently discovered by Urbanik.
}%\end subsection{Initial Description}
 
\subsection{Early Work}\label{sec:ew}
{
Zarankiewicz's conjecture was verified by Kleitman~\cite{Klei70:cnk5n} for the case when min($m,n$) $\leq$ 6, and by Woodall~\cite{Wood93:cogzcnc} for the case when $m$ = 7, $n \leq 10$. Unfortunately, the conjecture was thrown into question in 1965/66 when both Kainen and Ringel noticed a flaw in Zarankiewicz's paper, later reiterated by Guy~\cite{Guy69}. The flaw was the assumption by Zarankiewicz that among the $m$ graphs K$_{1,n}$ that compose the graph K$_{m,n}$, there will always be two that do not contain a crossing. Zarankiewicz's conjecture stands to the present as an upper bound on the crossing number of a complete bipartite graph, having been neither proven nor disproven for equality.

Guy continued to pursue the problem of Minimal Crossing Number of a complete graph, introducing an upper bound in 1960 that persists to the present~\cite{Guy60:acp}.

\begin{theorem}\label{thm: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}
He went on to conjecture that equality holds for all $n$. 

\begin{conjecture}\label{cj:Guy}[Guy]
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}
This conjecture has been proven for $n \leq 10$, but remains to be shown for $n > 10$. Guy has speculated privately that he now anticipates divergence from his conjecture with larger $n$. 

Surprisingly little work has been done on the problem of crossing numbers, considering its many applications in circuit design~\cite{lei83, lei84:nlbtvlsi}, graphics~\cite{bett99}, network configuration, etc. The explanation for this undoubtedly lies in the difficulty in making further progress. This difficulty became more understandable in 1983, when Garey and Johnson proved that the Minimal Crossing Number problem is NP-complete~\cite{gj83:cninpc}. Their proof consists of transforming a known NP-complete problem, the Optimal Linear Arrangement problem, into the Minimal Crossing Number problem. They suggested that the intractable nature of the Minimal Crossing Number problem meant that further research should be directed toward inexact methods that only estimate crossing numbers. Indeed, subsequent research tended to focus on related problems and subproblems and is difficult to synthesize into a coherent whole, whereas the attempt to search further for exact results for crossing number problems was largely abandoned.  
}%\end subsection{Early Work}
}% end \section{History of the Minimal Crossing Number Problem}
\section{Harris and Harris Algorithm}\label{sec:hh} 
{
\subsection{Introduction}\label{sec:hhintro}
{  
In 1996, the first algorithm to calculate the exact crossing number of a complete graph was proposed by Harris and Harris~\cite{hh96:apafctmcnoag}. The algorithm is based on a tree structure, using exhaustive depth-first search limited by branch-and-bound methodology. As it is the starting point for all the work to be discussed below, we will examine it now in some detail.  

} % end \subsection{Introduction}

\subsection{Edmonds' Rotational Embedding Scheme}\label{sec:eres}
{
A key part of the Harris and Harris algorithm is Edmonds' Rotational Embedding Scheme~\cite{edmo60:crps}. The scheme is used to determine the planarity of partial graphs prior to mapping to the tree structure. It is formally presented in~\cite{CHAR96}, pages 196-197 as Theorem 7.14, which will be excerpted here.

\begin{quote}
	Let G be a nontrivial connected graph with $V(G)$ (the vertex set of 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}$ in counterclockwise order about $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 of the vertices adjacent to $v_{i}$ and in
	counterclockwise order about $v_{i}$ are given by $\pi_{i}$.
	\end{quote}
	
The scheme is best illustrated with an example, taken from~\cite{hh96:apafctmcnoag}. 
Figure~\ref{fig:plembed} displays a planar embedding of a graph. The counterclockwise permutations associated with each of the vertices are as follows:
	    \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:plembed}
 \end{figure} 

These permutations allow us to determine the edges of the graph, and thereby the regions of the graph. As an example, we will use the permutations to determine the edges of the region bounded by (1,2), (2,4), and (4,1). The edges are 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 From the permutation $\pi_{2}$ determine which vertex follows
                        1; it is 4. Therefore the second edge is (2,4).

                \item From the permutation $\pi_{4}$ determine which vertex follows 2;
                        it is 1. Therefore the third edge is (4,1).
   
               \item From the permutation $\pi_{1}$ determine which vertex follows 4;  
                        it is 2. This yields edge (1,2), which was the original edge, so we are finished.
                \end{list}                                        
}                                                        
        \noindent         

The graph in Figure~\ref{fig:plembed} has four regions; three are obvious and the fourth is the external region bounded by (6, 5), (5, 4), (4, 3), (3, 2), (2, 1), and (1, 6). Notice that the external region must be traced counterclockwise in order for the permutations to define it, whereas all the other regions are traced clockwise.

Once the regions are identified and counted, Euler's formula can be employed to determine if a planar embedding exists. If Euler's formula is not satisfied, we know that one or more crossings occurred when the graph was drawn.
}% end \subsection{Edmonds' Rotational Embedding Scheme}
 
\subsection{Description of the Algorithm}\label{sec:dota}
{
The Harris and Harris algorithm commences by taking the unconnected vertex set of the graph and adding edges. After the addition of each edge, the Rotational Embedding Scheme is employed to count the resulting regions, and then Euler's formula is used to test for planarity of the resulting partial graph. Edges continue to be added until the partial graph is no longer planar, at which time the last edge is removed to return to the last planar configuration. This process is repeated for every permutation of the vertices. The result is all the partial graphs possible from that vertex set that have planar embeddings.

At this point the remaining search space is mapped onto a tree. The root of the tree has a branch for each of the planar partial graphs created above. Starting with the first branch of the tree, we begin the depth-first search process, building and searching simultaneously.

Depth-first search is a tree traversal algorithm that searches as deeply as possible into the tree for a solution before moving on to adjacent branches. Only after a terminal leaf is reached, which represents a solution for that branch of the tree, does the algorithm backtrack up to the previous division. Then, it again goes to the deepest position of the adjoining branch before backtracking. In this manner, the entire tree is exhaustively searched. 

The added wrinkle of branch and bound provides one method of improving efficiency. The current optimal solution is maintained as the search progresses, so that whenever that optimum is exceeded, the algorithm searches no deeper in the current subtree. Aborting the search prevents fruitless time spent exploring areas of the tree known not to contain a new optimum while still exhaustively searching all viable paths.

Beginning with the first embedding, we again add edges to the partial graph. This time, though, we know that each added edge must result in a crossing. Each level further down into the tree we go without finding our terminal vertex represents yet another crossing. As we progress downward, decisions must be made about which region and edge to cross at each level. Once the requirements of a good drawing are satisfied, a branch is created for every available region and edge combination we could cross on our journey to the desired vertex. For each region and exit edge, we create a new cross vertex at the point of the crossing. This allows the partial graph to remain planar, although with one vertex that is not a part of the graph, and one edge that is actually only an edge segment.

After the cross vertex is created, we check to see if we can connect from it to the terminal vertex directly. If so, we have reached a leaf. We count the number of levels, representing new cross vertices, and this value is the cost of reaching that vertex by that path. If more than one vertex needs to be connected to complete this partial graph, the cost is summed for each path and a starting optimum, or minimal crossing number is established. This becomes the bound as we move on to explore the next partial graph. 

Once the tree has been exhaustively searched, we have determined the overall minimal crossing number for the graph. There may be one or more embeddings that result in that crossing number; discovering which of these are isomorphic, and therefore not unique is a problem we will address below. 

Again, an example serves to clarify the process. This example, taken from~\cite{hh96:apafctmcnoag}, uses a K$_5$ graph, the first complete graph that has a crossing number greater than zero. This simple example has only one starting partial graph, shown in Figure~\ref{fig:partK5}. It is the result of connecting edges while confirming after each addition that the graph is still planar with Euler's formula.

\begin{figure}[!ht]
       \begin{center}
			 \includegraphics[width=3.0in]{ch2/K5planeChap2.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Partial Planar K$_{5}$ Graph}
       \label{fig:partK5}
\end{figure}
When we attempt to connect the final edge, from $i$ to $j$, Euler's formula tells us that the graph can no longer be embedded in the plane; a crossing has occurred. We backtrack and begin the depth-first search. Note that although other partial graphs could be drawn with differently numbered vertices remaining to be connected, they are all isomorphic to this one. 
                
Our next step is to connect all remaining edges, which in this example consists of only one edge, $i$ to $j$. Looking at Figure~\ref{fig:partK5}, we see three possible regions to cross to which vertex $i$ is adjacent, namely regions R1, R2, and R3. We begin by selecting R1. R1 has 3 edges but the constraints of drawing a good graph prevent us from crossing two of them, specifically the two incident with $i$. Thus edge $kl$ is selected, a cross vertex is created on this edge, and an edge segment is placed connecting the cross vertex with $i$ (Figure~\ref{fig:laydown}a). Next, we check whether the new cross vertex can be connected with $j$ while the graph remains planar.  In this instance, it can and so the edge segment is laid down and the edge from $i$ to $j$ is complete with one crossing (Figure~\ref{fig:laydown}b). As there are no more vertices to connect, the graph is complete with a crossing number of 1. The algorithm then backtracks and tests laying down an edge through each of the other two regions. Although it finds two more ways to draw the edge, it does not improve upon the crossing number of 1.

\begin{figure}[!ht]
       \begin{center}
			 \includegraphics[width=4.5in]{ch2/K5layEdgeChap2.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Completing Final Edge of K$_5$}
       \label{fig:laydown}
 \end{figure}
 
}%end \subsection{Description of the Algorithm}

} % end \section{Harris and Harris Algorithm}

 
 %parallel by Tadjiev and Harris~\cite{Tadj98:pcgvmcng,th97:pcmcng}.     
 
\section{Optimization of Harris and Harris}\label{sec:ohh}
 {
     
\subsection{Parallel Implementation}\label{sec:pi}
{
Exhaustive search algorithms can become computationally expensive as the search space grows. The Harris and Harris algorithm as presented above has only the branch and bound limitation in place, so the next obvious step in its evolution was to improve performance by further optimization. 

The first method chosen was to implement the algorithm in parallel, reported by Tadjiev and Harris~\cite{Tadj98:pcgvmcng, th97:pcmcng}. They reconfigured the algorithm to run on a network of Pentium 133 machines running Linux, linked with PVM in a host-node format. For simplicity, they chose to do a static partitioning of the search tree among the processors. A static system has a data set that is completely defined prior to run-time that can be evenly divided among the processors. Although the process ran faster in parallel for all graph families tested, meaningful improvement in performance required at minimum a K$_8$. As one might anticipate, speedup was improved by increasing the number of processors. Comparable results were seen with a Solaris/MPI system.
}%\end subsection(Parallel Implementation}

\subsection{Load-Balanced Parallel Processing with a Queuing \\ System}\label{sec:lbppwaqs}
{
It became apparent during the work described above that the processors were not finishing concurrently, the main drawback of a statically partitioned data set. One can envision an unbalanced tree in which static partitioning does not result in an even work load distribution among processors. Furthermore, a heterogeneous network cluster, which is not uncommon, can result in load imbalance even when the work load is evenly distributed. The next step then was to divide the work efficiently among processors to ensure that no processor is sitting idle while others work. This problem was tackled by Yuan, et al. using a generic work queuing system to provide dynamic load balancing ~\cite{Yuan2004:gqstsrrccnkn, ymfh:agqs}.

Work queues can be implemented in various ways, each with its own pros and cons. At one extreme is a central work queue managed by a master processor that distributes jobs to slave processors as they finish working and request them. This approach suffers from the delays inherent in having the entire system managed by a single processor. Bottlenecks can occur if multiple slaves request jobs at once, and the network load is heavy with job and control message passing. At the other extreme is the decentralized system, in which local processors manage their own work queues. The downside of this approach is its similarity to static partitioning. 

The system created by Yuan et al. is a balance between these two extremes. A master processor creates the jobs, defined as the smallest possible unit of work, and places them on a central queue. A job is dispatched to each processor, which places the job into its own local queue. In the course of performing its assigned work, the slave creates additional jobs that are added to its local queue. Further message passing occurs when a slave works through its job queue and becomes idle, as it requests more work from the central queue. Alternatively, if the local queue overflows, a user-defined parameter,  as jobs are created and added to it, the slave sends work back to the central queue for redistribution. The primary downside to this approach, not surprisingly, is the amount of message passing network traffic it creates.
 
Several interesting results were found running the crossing number problem in this parallel generic queuing system. Like a government bureaucracy, the more processors that are used in the network, the more jobs that are created and the higher the volume of network traffic, with the result being little or no improvement in run time over a smaller parallel system~\cite{Yuan2004:gqstsrrccnkn}. Nonetheless, with an optimal number of processors and optimal queue size, shorter run times were seen than without load balancing.

}%\end \subsection{Load-Balanced Parallel Processing with a Queuing System}

\subsection{Graph Isomorphism}\label{sec:gi}
{
As per Definition~\ref{def:isomorphic}, we describe two graphs as isomorphic if there exists a one-to-one mapping of their vertex sets that preserves adjacency. Numbering of vertices is an arbitrary construct that allows us to define regions, but has no bearing on the underlying graph structure. As one can imagine, larger graphs with many vertices, some native and some crossing, can be created from a myriad of paths, which results in graphs that not only have differently numbered vertices  but that may look completely different from each other when drawn. Many of these graphs will in fact be isomorphic. Figure~\ref{fig:isomorph} demonstrates the difference between isomorphic and nonisomorphic graphs; Figures~\ref{fig:isomorph}a and b are isomorphic to each other, but Figure~\ref{fig:isomorph}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{Comparison of Isomorphic and Nonisomorphic Graphs}
       \label{fig:isomorph}
\end{figure}
The search space can be significantly reduced by selecting only one member of each isomorphic family to test for the next higher value of $n$. Table~\ref{tbl:isofamilies} displays the relationship between the total number of minimal graphs and the number of isomorphic families found for $5 \leq n \leq 10$.

\begin{table}[h]
	\centering
		\begin{tabular}{|c|cccccc|} \hline
	$n$ 		         &  5 & 6 &  7 &  8 &    9 &    10   \\ \hline
	Graphs generated & 12 & 4 & 76 & 20 & 4,590 & 56,618  \\ \hline
	Iso families     &  1 & 1 &  5 & 3  & 1,453 &  5,679  \\ \hline
		\end{tabular}
	\caption{Relationship Between Total Minimal Graphs and Isomorphic Families}
	\label{tbl:isofamilies}
\end{table}   

Determining graph isomorphism is an intensive process~\cite{fort96:gip}. One of the best current methods uses a canonical labeling for each graph to be tested. Graph G is isomorphic to graph H if and only if the canonical label for G is identical to the canonical label for H. The most widely used algorithm for canonical labeling is called $NAUTY$, standing for "No AUTomorphisms, Yes?"~\cite{m81:pgi} Written by Brendan McKay, the software package that implements the $NAUTY$ algorithm has been modestly described by its author as the "world's fastest isomorphism testing program." 
} % end \subsection{Graph Isomorphism}

\subsection{Region Restriction}\label{sec:rr}
{
A further optimization was implemented by Fredrickson et al~\cite{Fred06:otcnocg, fyh:atsrrfctcnok}. They added another constraint to the definition of a good drawing: they specified that no region of the graph should be crossed more than once by a single edge. 

As an example, consider the graphs in Figure~\ref{fig:regrestr1} below. Figures~\ref{fig:regrestr1}a, b, and c meet the definition of a region restricted good drawing for placement of edge $uv$ and would be generated under the new algorithm. Figure~\ref{fig:regrestr1}d does not meet the definition and would no longer be generated. Note that region restriction does not prevent non-minimal graphs from being drawn, but it does eliminate an entire class of graphs that cannot be minimal. Proof that restricting an edge from reentering a previously entered region does not prevent any possible minimal graphs from being generated can be found in~\cite{Fred06:otcnocg}.

\begin{figure}[!ht]
       \begin{center}
       	\includegraphics[width=4.0in]{ch2/gdpeChap3.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Region Restricted Good Drawings of Edge $uv$ (a,b,c) and Not Good Drawing (d)}
       \label{fig:regrestr1}
\end{figure}
        
To illustrate further, consider Figure~\ref{fig:regrestr2}. A branch of the search tree is created for every possible path between $u$ and $v$. Thus an edge will be begun or continued through every available region at each level, as seen for the starting regions in Figure~\ref{fig:regrestr2}a. Any edge entering a region adjacent to one it has already passed through after having crossed a subsequent region (Figure~\ref{fig:regrestr2}b) will have more crossings than an edge that entered that region directly (Figure~\ref{fig:regrestr2}c).  
        
\begin{figure}[!ht]
       \begin{center}
       	\includegraphics[width=4.0in]{ch2/paths4uv.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Possible Paths for Laying Down Edge $uv$}
       \label{fig:regrestr2}
\end{figure}

Fredrickson later summarized the optimization into a new definition of a good drawing of a graph~\cite{Fred06:otcnocg}:

\begin{definition}\label{def:regionrestrict}
Let
\begin{center} $f : u = u_0, e_1, u_1, e_2, …, u_{k-1}, e_k, u_k = v$ 
\end{center}
denote the $u-v$ path laid down in graph G where $ei$ is an edge segment through one region of G. Let H = G + f. The graph H is a region restricted good graph if every region of H has at most two vertices of f on its boundary.
\end{definition}
She then provided 

\begin{theorem}\label{thm:rr}[Fredrickson]
Employing the definition of a region restricted good drawing of a graph while creating minimal K$_n$ from minimal K$_{n-1}$ does not eliminate any possible minimal graphs from being generated.	
\end{theorem}

The authors of~\cite{Fred06:otcnocg, fyh:atsrrfctcnok, Yuan2004:gqstsrrccnkn} found that the substantial reduction in search space resulting from tightening the definition of a good drawing (see Table~\ref{tbl:rrvsnorr}) produced order of magnitude improvements in run time up to K$_8$. K$_9$ did not complete running after several weeks, and remained to be solved after further optimization. Additional processors resulted in further run time improvements.

\begin{table}[ht]
	\begin{center}
	\begin{tabular}{|c|r|r|r|}\hline
	{\bf Vertices} & {\bf $\nu(K_{n})$}	& {\bf Good Graph} & \multicolumn{1}{c|}{{\bf Restricted}} \\
	{\bf ($n$)}	&		&	& {\bf Good Graph} \\ \hline
	5	& 1		& 3		& 3 \\ \hline
	6 	& 3 		& 203 		& 71 \\ \hline
	7 	&9 		& 1,498,775 	& 19,979 \\ \hline
	8	& 18		& *		& 46,697,854 \\ \hline
	\end{tabular}
	\end{center}
	\caption{Number of Jobs Required to Find $\nu$(K$_n$) With and Without Region Restriction }
	\label{tbl:rrvsnorr}
	\end{table}	
}%\end subsection{Region Restriction}

\subsection{Radical Region Restriction}\label{sec:rrr}
{
One final optimization was introduced prior to the work to be presented here. A further restriction on placement of edges through regions, known as radical region restriction, was presented in~\cite{Fred06:otcnocg}. Radical region restriction is based on preliminary analysis of the shortest path from $u$ to $v$, in terms of the number of regions crossed. It determines, for each of the $n$ - 1 edges that need to be created, the minimal number of regions that need to be crossed to complete the edge. The algorithm only follows branches of the tree that do not exceed the minimum. Logically, crossing the fewest number of regions results in the fewest number of edge crossings. 
	
This refinement is illustrated in Figure~\ref{fig:radical}. Four of the ten possible $uv$ edge placements for the given graph are displayed.
\begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=5.0in]{ch2/radical.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Options for Placement of Edge $uv$}
       \label{fig:radical}
 \end{figure}
Only Figures~\ref{fig:radical}a and b have paths that cross the minimum number of regions (two) and therefore have the fewest edge crossings (one). The other figures display paths that cross more regions (three), result in two edge crossings each, and could not contribute to a minimal graph. Radical region restriction would prevent the creation of these paths. 

When radical region restriction was used to generate minimal K$_n$ graphs up to K$_{10}$, substantial reduction in running time was seen as compared with basic region restriction (Table~\ref{tbl:radruntime})~\cite{Fred06:otcnocg}. Even with radical region restriction, minimal K$_{10}$ required approximately a week to generate owing to the large number of isomorphic K$_9$s it had to start with (1453). 

	\begin{table}[ht]
	\begin{center}
	\begin{tabular}{|c|r|r|r|}\hline
	{\bf Vertices} & {\bf $\nu(K_{n})$}	& {\bf Region} & \multicolumn{1}{c|}{{\bf    Radical Region}} \\
	{\bf (n)}	&		& \bf    Restriction	& {\bf Restriction} \\ \hline
		8	 & 18		& 2 hr 36 min		& 5 min \\ \hline
		9  & 36    &  $>> 1$ week  & 8 min \\ \hline
		10 & 60    &  unknown      & $\approx 1$ week \\ \hline
	\end{tabular}
	\end{center}
	\caption{Runtime for Region Restriction {\it versus} Radical Region Restriction}
	\label{tbl:radruntime}
	\end{table}	
}%\end subsection{Radical Region Restriction}
 
}%\end \section{Optimization of Harris and Harris}
 
\section{Bipartite Graphs}\label{bg}
{
Before presenting the current work, we will briefly digress and consider bipartite graphs. As mentioned earlier, the original description of the crossing number problem involved a complete bipartite rather than a complete graph. The complete bipartite graph representing Tur\'{a}n's Brick Factory Problem can be visualized as in Figure~\ref{fig:bipartiteTuran}, adapted from Richter and Thomassen~\cite{rt97:rbcnccbg}, where vertices 1, 2, and 3 represent the brick ovens, and are the first partite set, and vertices 4, 5, 6, and 7, the second partite set, represent the yards where the bricks were stacked for storage.

\begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=4.0in]{ch2/bipartiteTuran.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Complete Bipartite Graph K$_{3,4}$ Illustrating Tur\'{a}n's Brick Factory Problem}
       \label{fig:bipartiteTuran}
 \end{figure}
This representation can be redrawn as a minimal graph (Figure~\ref{fig:minbipartite}) that has a crossing number of 2. It is clear from these two representations of K$_{3,4}$ that the specific drawing in the plane is critical with respect to crossing number, and may not be immediately obvious, even for small $m,n$.

\begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=4.0in]{ch2/minbipartite.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Minimal Complete Bipartite Graph K$_{3,4}$}
       \label{fig:minbipartite}
 \end{figure} 

Bipartite graphs are useful in VLSI routing simulations~\cite{sssv00:nlbbcnwa}, and might be of value in any situation where interconnections occur between two groups of nodes, but not within the groups, such as electrical wiring for example. A discussion of the relations between the crossing numbers of complete and complete bipartite graphs can be found in~\cite{rt97:rbcnccbg}.

There are several interesting properties of bipartite graphs, summarized by Woodall in his work confirming Zarankiewicz's conjecture for m = 7, $n \leq 10$~\cite{Wood93:cogzcnc}. These are given in the following theorems:

\begin{theorem}\label{thm:bip1}[Woodall]
Every G = K$_{m,n}$ with crG = $k$ contains a drawing of K$_{m-1,n}$ with a number of crossings cr $\leq$ $k (m - 2)  / m$.	
\end{theorem}

\begin{theorem}\label{thm:bip2}[Woodall]
If m is even and the Zarankiewicz conjecture holds for K$_{m-1,n}$, then it holds for K$_{m,n}$.
\end{theorem}
Theorem~\ref{thm:bip2} allows us to limit our consideration to graphs where both $m$ and $n$ are odd. 
	
Minimizing the crossing number of a complete bipartite graph is a sister problem to that of the crossing number of a complete graph. It is desirable that any solution to the crossing number problem be applicable to the bipartite family of graphs as well. Preferably, a general solution applicable to many graph family problems could be found.

}%\end section{Bipartite Graphs} 
%\end chapter
\newpage
 
 
 
 
 
 	
 	