

\documentstyle{article}
\textwidth=6.5in
\textheight=9in
\evensidemargin=0in
\oddsidemargin=0in
\topmargin=-0.3in
\topskip=0pt
\baselineskip=12pt
\parskip=10pt 
\parindent=1em

\begin{document}

\begin{center}
\Large
{\bf Calculation of the Minimum Crossing Number of a Graph}

\normalsize
Frederick C. Harris, Jr. \\
Department of Computer Science \\
University of Nevada \\
Reno, NV 89557 \\
fredh@cs.unr.edu
\end{center}

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 Edmond's 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.
\end{document}
