%  DO NOT MODIFY ANY OF THE COMMANDS LISTED BELOW!!!

\documentstyle[11pt,twoside]{article}
\textwidth = 4.625in
\textheight = 7.25in

\makeatletter
\newcommand{\ps@foot}{\def\@oddhead{}\def\@evenhead{}\def\@evenfoot{}
\def\@oddfoot{\mbox{\footnotesize Graph Theory, Combinatorics,
Algorithms, and Applications, 1996}\hfill\thepage}}

\newcommand{\ps@runner}{\def\@oddhead{\mbox{}\hfill\shorttitle\qquad\thepage}
\def\@evenhead{\thepage\qquad\shortauthor\hfill\mbox{}}\def\@evenfoot{}
\def\@oddfoot{}}

\def\maketitle{\par
 \begingroup
 \def\@makefnmark{\hbox 
 to 0pt{$^{\@thefnmark}$\hss}} 
 \if@twocolumn 
 \twocolumn[\@maketitle] 
 \else \newpage
 \global\@topnum\z@ \@maketitle \fi\thispagestyle{foot}\@thanks
 \endgroup
 \let\maketitle\relax
 \let\@maketitle\relax
 \gdef\@thanks{}\gdef\@author{}\gdef\@title{}\let\thanks\relax}
 
 \pagestyle{runner}
\makeatother



%%%%%%%%% Begin Inserting Your Paper Below this Point %%%%%%%%%%%%%%%%

\setcounter{page}{1}         % Insert the BEGINNING page number here

\input{psfig}
\begin{document}

\newcommand{\shortauthor}{Frederick C. Harris Jr. and Cynthia R.  Harris}
\newcommand{\shorttitle}{A Proposed Algorithm for Calculating the Crossing Number}

\title{A Proposed Algorithm for Calculating the Minimum 
Crossing Number of a Graph}
\author{
Frederick C. Harris, Jr. \\
Department of Computer Science \\
\hspace*{1in}\\
Cynthia R. Harris\\
Department of Mathematics\\
\hspace*{1in}\\
University of Nevada \\
Reno, NV 89557 \\
fredh@cs.unr.edu}
%Name(s) of the Author(s)
% \footnotemark               % Inserts a footnote mark (deactivated)
%                              % Remove the %-symbol in front if you
%                              % plan to have an Author's Footnote. 
%\\ Affiliation of the Author(s)}
\date{ }                      % Keep empty to ensure the date is not printed
\maketitle
% \footnotetext{Place the Author's footnote (if it exists) here}
                              % Remove the %-symbol to reactive the command



% From here on, write your paper as you normally would.
% The result upon compilation should look like the sample
% paper that has already been distributed.


\bibliographystyle{plain}

\begin{abstract}
	In this paper we present a branch-and-bound algorithm for
	finding the minimum crossing number of a graph.  
	We begin with the vertex set and add edges by selecting every
	legal option for creating a crossing or not.  After each edge
	is added we determine if the resulting partial graph is
	planar.  We continue adding edges until either all edges have
	been added or we reach a point where the graph cannot be
	completed as started.  At this point we backtrack to
	see if the graph can be drawn with fewer crossings by selecting
	other options when adding edges.

	\noindent
	{\bf keywords:} Crossing Number, Algorithm
\end{abstract}



\section{Introduction}

	Determining the crossing number of a graph is an important 
	problem with applications in areas such as circuit design and
	network configuration~\cite{leighton83:ciivlsi}.  
	It is this importance that has driven 
	our work in finding the minimum crossing number of a graph.

	Informally, the {\it crossing number} of a graph G, 
	denoted $\nu (G)$, is the minimum number of crossings among all
	good drawings of G in the plane, where a good drawing has the
	following properties:

		%\noindent
		(a) No edge crosses itself

		%\noindent
		(b) No pair of adjacent edges cross

		%\noindent
		(c) Two edges cross at most once

		%\noindent
		(d) No more than two edges cross at one point


	\vspace{12pt}

	Although the problem is easily stated and has been well
	studied, not much is known about the general solutions.  
	Erd\"{o}s and Guy~\cite{eg:cnog} put together a survey 
	of what was known in 1973,
	and Turan discussed it via his Brick Factory Problem
	\cite{turan:1977}.  However, it was not until 1983 that Garey
	and Johnson \cite{gj83:cninpc} proved that finding the minimum
	crossing number of a graph  was an NP-Complete problem.  
	Because of the difficulty of this problem, work turned away 
	from finding the minimum crossing number of a graph to 
	sub-problems and other related problems.  

	With regard to the sub-problems, there has been work on product
	graphs ranging from the product of $C_{n}$ and graphs of order
	four~\cite{br80:otcnopocagoof} to 
	$C_{3} \times C_{n}$~\cite{rb78:tcnoc3xcn}, 
	$C_{4} \times C_{4}$~\cite{dr95:tcnoc4xc4}, 
	$C_{5} \times C_{5}$~\cite{rt95:iocsatcnoc5xc5}, 
	and $C_{5} \times C_{n}$~\cite{krs96:tcnoc5xcn}.   
	There has also been work in the area of bipartite graphs with
	the results of 
	$K_{3,n}$~\cite{rs96:tcnok3nias},
	$K_{5,n}$~\cite{kleitman71:tcnok5n}, and the torroidal crossing
	number of $K_{m,n}$\cite{gj69:ttcnokmn} having been found.
	In 1991 Beinstock published work \cite{bienstock91:sphcnp}
	relating the crossing number of a graph to the arrangement of
	pseudolines,a topic well studied by combinatorialists.

	There have also been several related problems that have been
	studied over the years.  Some of these range from the rectilinear
	crossing
	problem~\cite{GUY72,thomassen88:rdog,th96:apsoaffmormcp} to the
	maximum crossing number of a graph or
	subgraph~\cite{ghprs:citcg,hks73:tgwahcn} to the thrackle
	conjecture~\cite{cottingham:dissertation}.

	We now wish to turn the attention of this paper back to the
	minimum crossing number of a graph.  In Section~\ref{sec:def}
	we review some notation and definitions we build on throughout
	the paper.  In Section~\ref{sec:res} we outline Edmonds'
	Rotational Embedding Scheme which gives us the foundation
	for our proposed algorithm.  In Section~\ref{sec:bb} we
	discuss depth-first search and branch-and-bound algorithms and
	in Section~\ref{sec:pa} present our proposed algorithm.
	Conclusions and future work are presented in
	Section~\ref{sec:fw}.


\section{Notation and Definitions}\label{sec:def}

	We now define some terms from topological graph theory which
	will be used through the rest of this paper.  These
	definitions are as in \cite{CHAR86}.

	For our purposes, a {\it compact-orientable 2-manifold}, or
	simply a surface, may be thought of as a sphere or a sphere
	with handles.  The {\it genus} of the surface is the number of
	handles.

	An {\it embedding} of a graph G on a surface S is a drawing of
	G on S in such a manner that edges intersect only at a vertex
	to which they are both incident.

	A region in an embedding is called a {\it 2-cell} if any simple
	closed curve in that region can be continuously deformed or
	contracted in that region to a single point.  An embedding is
	called a {\it 2-cell embedding} if all the regions in the
	embedding are 2-cell.

	An algebraic description of a 2-cell embedding was given by
	Dyck~\cite{dyck:1888} and Heffter\cite{heffter:1891}.  This
	description is referred to as a Rotational Embedding Scheme
	which will be covered in Section~\ref{sec:res}.

	Finally, the relationship between the number of regions of
	a graph and the surface on which it is embedded is described by
	the well-known generalized {\it Euler's Formula}~\cite{CHAR86}:

		\begin{quote}
		Let G be a connected graph with $p$ vertices and $q$ edges
		with a 2-cell embedding on the surface of genus $n$
		having $r$ regions.  Then $p - q + r = 2 - 2n$.
		\end{quote}

	
\section{Rotational Embedding Scheme}\label{sec:res}

	With these definitions as background, we now look at the
	Rotational Embedding Scheme, first formally introduced by
	Edmonds~\cite{edmonds:1960} in 1960 and then discussed in
	detail by Youngs~\cite{youngs63:miatgoag} a few years later.  The
	following is the formal statement of the Rotational Embedding
	Scheme as given in \cite{CHAR86} on pages 130--131.

	\begin{quote}
	Let $G$ be a nontrivial connected graph with $V(G) = \{v_{1},
	v_{2},$ $\ldots, v_{p}\}$.  For each 2-cell embedding of $G$ on a
	surface there exists a unique $p$-tuple $(\pi_{1}, \pi_{2},
	\ldots, \pi_{p})$, where for  $i = 1, 2,$ $\ldots, p$, $\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 $p$-tuple $(\pi_{1}, \pi_{2}, \ldots,
	\pi_{p})$, there exists a 2-cell embedding of $G$ on some surface
	such that for $i = 1, 2, \ldots,p$ the subscripts of the
	vertices 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}[h]
        \centerline{\psfig{figure=house.ps,height=1.5in}}
	\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 From permutation $\pi_{2}$ determine which vertex follows 
			1; it is 4.  Therefore the second edge 
			is (2,4). 
		\item From permutation $\pi_{4}$ determine which vertex
			follows 2; it is 1.  Therefore the third edge is (4,1). 
		\item From 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 region we considered is bounded by the edges (1,2), (2,4),
	and (4,1).  The other regions and associated edges can be found in a 
	similar manner.

	The important thing to note is the converse
	portion of the Rotational Embedding Scheme - that every 
	collection of vertex permutations corresponds to 
	an embedding on some surface.  Given a set of permutations, 
	we can trace the edges of the regions and determine the genus 
	of the surface on which the graph is embedded.

	One of the authors developed a computer program to 
	generate all vertex permutation schemes for a graph \cite{lr:cnopg}.
	The program then counts the regions of the resulting
	embedding and, using Euler's formula, determines if a given graph
	has a planar embedding.  The code for this program can be found
	in \cite{lovegrove:masters} and has motivated us to keep track
	of regions in the construction of a graph drawing, which is the
	basis for our proposed algorithm presented in
	Section~\ref{sec:pa}.

\section{Depth-First Search with Branch-and-Bound} \label{sec:bb}

	If the solution space of a problem can be mapped to a tree, where
	each interior vertex is a partial solution, edges toward the
	leaves are options that refine the partial solution, and the leaves
	are complete solutions, then there are various algorithms that
	can search the tree to find the optimal solution.  A depth-first 
	search (DFS) algorithm is one such algorithm which, as
	its name implies, 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.

	The branch-and-bound portion allows us to change one simple
	part of the DFS algorithm.  When the cost to get to a vertex
	$v$ exceeds the cost of the current optimal solution, we then 
	tell the DFS
	algorithm not to traverse the subtree having $v$ as its root.

	This method exhaustively covers the entire search space even
	after finding an initial solution without covering
	those sections of the search space that lead to solutions that
	are guaranteed to cost more than the current optimal solution.  
	When the entire tree is covered, the current optimal solution 
	is the globally optimal solution.

\section{Proposed Algorithm}\label{sec:pa}

	For our proposed algorithm we map the solution space from the
	crossing number problem onto a tree and search for the minimum
	crossing number with a DFS with branch-and-bound.  The root of
	our tree corresponds to the vertex set.  The root has $|E|$
	(the number of edges) branches coming out of it.  Each branch
	corresponds to the first edge that is added to the graph.  The
	next level of the tree has $|E|-1$ branches coming out of each
	node.  The tree is $|E|$ levels deep, and the path to each leaf
	corresponds to a unique permutation ordering for the edges.

	We begin by selecting edge $(i,j)$.  We use Euler's Formula to
	determine if the edge can be added from vertex $i$ to vertex
	$j$ without any crossings. (We do this by keeping track of the
	number of regions in the graph as it is constructed.)  If so, we
	add the edge and select the next edge.  If not, we choose an
	edge that has already been added to cross.  (This may be the
	only edge crossed, or the first edge in a long list of edges to
	be crossed).  Once we decide that edge $(i,j)$ is to cross edge
	$(k,l)$ we create a new vertex $m$, remove edge $(k,l)$, add
	partial edges $(k,m)$, $(m,l)$, and $(i,m)$, and then draw edge
	$(m,j)$ in the same fashion.

	When drawing an edge, we remember that an edge cannot cross
	itself,  that no pair of adjacent edges cross, and that two
	edges cross at most once.  We also keep track of all partial
	edges and remember that they are actually {\it part} of an
	edge.  In the scenario described in the previous paragraph, we
	would have to remember that edge $(i,m)$ is part of edge $(i,j)$.

	Let us demonstrate the algorithm with $K_{5}$ as our example.
	$K_{5}$ has 10 edges. The first 9 are added directly without
	crossing another edge.  This partial graph is shown in
	Figure~\ref{fig:k5b}.  When the last edge is considered,
	Euler's Formula indicates that the resulting graph cannot be
	embedded on the plane.  
	\begin{figure}[bht]
	\vspace*{0.1in}
        \centerline{\psfig{figure=k5-b.ps,height=2in}}
	\caption{First 9 edges of $K_{5}$ with no crossings}
	\label{fig:k5b}
	\end{figure}
	Therefore, we must add the edge
	$(i,j)$ with at least one crossing.



	At this stage we select edge $(k,l)$ to cross, insert vertex
	$m$,  remove edge $(k,l)$, and add partial edges $(k,m)$,
	$(m,l)$, and $(i,m)$.  The graph is as shown in
	Figure~\ref{fig:k5c}.  Once these partial edges have been drawn
	the algorithm tries to draw the rest of edge $(i,j)$ without any
	crossings and succeeds.  Figure~\ref{fig:k5d} shows this
	drawing of $K_{5}$ with one crossing.
	\begin{figure}[h]
	\vspace*{0.1in}
        \centerline{\psfig{figure=k5-c.ps,height=2in}}
	\caption{The first part of the last edge is drawn for $K_{5}$}
	\label{fig:k5c}
	\end{figure}
	\begin{figure}[h]
	\vspace*{0.1in}
        \centerline{\psfig{figure=k5-d.ps,height=2in}}
	\caption{One drawing of $K_{5}$ with 1 crossing at m}
	\label{fig:k5d}
	\end{figure}

	The algorithm then backtracks with a new bound of one
	crossing.  It will then back up through the rest of the tree
	and try all other parts of the tree.  However, once the
	algorithm has determined that it cannot add an edge without
	any crossings, it will not try any further down that branch
	since the best drawing so far has one crossing.  It will finish
	when it has exhausted all possibilities. In the case of $K_{5}$,
	no possibility  will result in a drawing with zero crossings.

\section{Conclusions and Future Work}\label{sec:fw}

	We have presented a proposed algorithm for calculating the
	minimum crossing number of a graph.  This could also be
	extended to finding the maximum crossing number by making minor 
	modifications to the search algorithm. We could also find all
	possible drawings with the minimum crossing number, or we could
	remove the bound and enumerate all possible drawings of a graph.

	The first step in the future work is to implement
	this algorithm and test it on some known graphs.  Once that is
	accomplished, we would be able to determine if the order of the
	edges matters in reaching the correct answer more quickly.  The
	order may be important for graphs in general, but it may not
	for certain classifications (such as $K_{n}$).  Once that has
	been determined, we would like to calculate the crossing number
	for several families which are important in 
	circuit design, such as $K_{n}$, $K_{(m,n)}$, and various
	others.  The last item on the list (which would not be done
	last) would be to parallelize this process.  This would greatly
	speed up the calculations since parallel DFS branch-and-bound 
	algorithms can achieve super-linear speedup.


%\section*{Acknowledgments}
%	We would like to acknowledge the referees comments, whose
%	inclusion have helped to make this a better paper.

\baselineskip=12pt
\parskip=0pt 
\parsep=0pt
\itemsep=0pt
\bibliography{/staff/fredh/papers/bibdir/xing,/staff/fredh/papers/bibdir/fredh}
\end{document}
