%  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 crossing number of a graph.  
	%Informally the
	%crossing number of a graph is the minimum number of crossings
	%required in a `good drawing' of a graph on the plane, where a
	%`good drawing' has the following properties: no edge crosses
	%itself, no pair of adjacent edges cross, two edges cross at
	%most once, and no more than two edges cross at a point.
	%
	We begin with the vertex set and add edges.  After adding each
	edge we use Edmonds' Rotational Embedding Scheme to determine
	if the resulting partial graph is planar.  We continue until no
	more edges can be added and the partial graph remain planar.
	At this point we lay down the rest of the edges one at a time,
	adding vertices of degree 4 where crossings occur, thereby
	keeping the partial graph planar.  Once all the edges are down,
	we begin backtracking to see if the graph can be drawn with
	fewer crossings by selecting other options when laying down
	edges.

	%\noindent
	%{\bf keywords:} Crossing Number
\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.  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 it.  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.  When
	this happened, work turned away from finding the minimum
	crossing number of a graph to other related problems.  These
	have ranged from a return to the rectilinear crossing
	problem~\cite{GUY72,th96:apsoaffmormcp} to the maximum crossing
	number of a graph or subgraph~\cite{ghprs:citcg}, to the thrackle
	conjecture~\cite{cottingham:dissertation}.

	We now wish to turn the attention of this paper back to the
	minimal 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 is a vital part of 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.  In general 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 observed 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}

	And 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 a 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 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}
        \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 Go to permutation $\pi_{2}$ and find out who follows 
			1, and it is 4.  Therefore the second edge 
			is (2,4). 
		\item Go to permutation $\pi_{4}$ and find out who follows 2, 
			and it is 1.  Therefore the third edge is (4,1). 
		\item Go to permutation $\pi_{1}$ and find out who follows 4 
			and it is 2.  This yields edge (1,2) which 
			was the original edge so we are finished.
		\end{list} 
	}
	\noindent
	The region we looked at was bounded by the edges (1,2), (2,4),
	and (4,1).  The other regions and edges can be found in a 
	similar manner.

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

	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 we will make extensive use of
	it in Section~\ref{sec:pa}.

\section{Depth First Search 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 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.  However, it does not cover
	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 are going to map the solution
	space from the crossing number problem onto a tree and search
	for the minimum crossing number with a branch and bound DFS.
	First we begin with the vertex set for the graph in question
	and begin to add edges.  After each edge is added we determine
	whether the partial graph is still planar.  This is done by
	using the Rotational Embedding Scheme code described in
	Section~\ref{sec:res}.  Once we cannot add any edges and keep
	the partial graph planar we are ready to begin our mapping to
	the tree.

	At this stage our partial graph is the root of our tree.  The
	first option we have is the many different ways to draw this
	graph.  The code described in Section~\ref{sec:res} will return
	all possible planar embeddings of the partial graph.
	Therefore, the root of the tree has a branch for each possible
	embedding.

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

	For all the rest of the edges we lay them down in a similar
	manner, and when we have finally laid them all down we have
	reached a leaf in the tree.  At this point we have a cost for
	the current solution which is the number of cross vertices we
	have added.  This number of crossings becomes the new bound.
	The DFS continues by backing up and trying other decisions in
	the tree using the bound as a stopping criteria.  We proceed
	until the entire solution space is traversed.

	In order to understand this, let us walk through the algorithm
	with $K_{5}$ as our example. In Figure~\ref{fig:k5b} we have the
	vertex set for the graph with all the edges added to the graph 
	while it can still remain planar.

	\begin{figure}[h]
        \centerline{\psfig{figure=k5-b.ps,height=2in}}
	\caption{Planar portion of $K_{5}$}
	\label{fig:k5b}
	\end{figure}

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

	\begin{figure}[h]
        \centerline{\psfig{figure=k5-c.ps,height=2in}}
	\caption{Beginning to lay down the alst edge for $K_{5}$}
	\label{fig:k5c}
	\end{figure}

	\begin{figure}[h]
        \centerline{\psfig{figure=k5-d.ps,height=2in}}
	\caption{One drawing of $K_{5}$ with 1 crossing}
	\label{fig:k5d}
	\end{figure}

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

	We have presented a proposed algorithm for calculating the
	minimal crossing number of a graph.  This could also be
	extended to finding the maximal crossing number by making minor 
	modifications to the search algorithm.

	The first step in the future work is obviously 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 matter in reaching the correct answer.  The order may
	be important for graphs in general, but it may not for certain 
	classifications.  Once that has been determined, we would like
	to calculate the crossing number for several families which 
	are very important when looking at 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 branch and bound DFS algorithms can achieve 
	super-linear speedup.

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