\documentstyle[11pt]{article}
\textwidth=6in
\textheight=9in
\evensidemargin=0.5in
\oddsidemargin=0.5in
\topmargin=-0.375in
\topskip=0pt
\parindent=3em
\baselineskip=24pt

\input{psfig}
\begin{document}
\bibliographystyle{plain}

\Huge 

%
% Title Page
%

\vspace*{\fill}
\begin{center}
A Proposed Algorithm \\for Calculating \\
the Minimum Crossing Number\\
 of a Graph\\
\quad \\
\quad \\
Frederick C. Harris, Jr.\\
Department of Computer Science\\
\quad \\
Cynthia R. Harris\\
Department of Mathematics\\
\quad \\
University of Nevada\\
Reno, Nevada 89557\\
fredh@cs.unr.edu
\end{center}
\vspace*{\fill}

\newpage
\noindent
I.  Problem Statement 

               \vspace{0.25in}
 
	\begin{itemize}
	\item Informally, the {\bf crossing number} of a graph $G$, denoted 
		$\nu(G)$, is  the minimum number of crossings among all
		good drawings of $G$ in the plane.

               \vspace{0.25in}

	\item 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

	\end{itemize}

\newpage
\noindent
II. History
	
               \vspace{0.25in}

	\begin{itemize}
	\item Erd\"{o}s and Guy put
        together a survey of what was known in 1973 \cite{eg:cnog}

               \vspace{0.25in}

	\item Turan discussed it via his Brick Factory Problem 
        \cite{turan:1977}

               \vspace{0.25in}

	\item In 1983 Garey
        and Johnson \cite{gj83:cninpc} proved that finding the minimum
	\\ crossing number of a graph  was an NP-Complete problem

\newpage
	\item Work then moved away from the \\ exact solution to:

               \vspace{0.25in}

		\begin{itemize}
		\item Approximations \cite{GUY72}

                \[ \nu (K_{n}) \leq \frac{ \lfloor \frac{n}{2} \rfloor
		\lfloor \frac{n-1}{2} \rfloor
                \lfloor \frac{n-2}{2} \rfloor \lfloor \frac{n-3}{2}
		\rfloor}{4}
                \]


               \vspace{0.25in}

		\item Rectilinear crossing
		number~\cite{GUY72,th96:apsoaffmormcp}

		{ \LARGE
                %insert Guy's formula here
                \[ \bar{\nu}(K_{n}) \leq \lfloor \frac{(7n^{4} - 56n^{3}
		+ 128n^{2} + 48n \lfloor \frac{(n-7)}{3}\rfloor + 108)}
                {432} \rfloor \]
		}

               \vspace{0.25in}

		\item Finding the maximum crossing number of a graph,
		or a subgraph, and solving the thrackle conjecture
		 \cite{cottingham:dissertation}

		\end{itemize}
	\end{itemize}

\newpage
\noindent
III. Notation and Definitions

        \vspace{0.25in}
	\begin{itemize}
	\item {\bf compact-orientable 2-manifold} -- \\ (or simply a surface) --
		may be thought of as a sphere, or a sphere with handles.

	\vspace{0.25in}
	\item {\bf genus} -- the number of handles

        \vspace{0.25in}
	\item {\bf embedding} --  a drawing of G on a surface S in such a 
		manner that edges intersect only at a vertex
        	to which they are both incident

        \vspace{0.25in}
	\item {\bf 2-cell} --  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


	\newpage
        \vspace{0.25in}
	\item {\bf 2-cell embedding} --  An embedding is called a 
		{\it 2-cell embedding} if all the regions in the
		embedding are 2-cell.

        \vspace{0.25in}

        An algebraic description of a 2-cell embedding was observed by
        \cite{dyck:1888} and \cite{heffter:1891}.  This description is
        referred to as a Rotational Embedding Scheme.

        \vspace{0.25in}
	\item {\bf Euler's Formula} --   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{itemize}



\newpage
\noindent
IV. Rotational Embedding Scheme

	\begin{itemize}
	\item First formally introduced by Edmonds in 
	1960~\cite{edmonds:1960} and discussed in detail by 
	Youngs~\cite{youngs63:miatgoag} a few years later.

        \vspace{0.25in}
	\item As given in Chartrand and Lesniak~\cite{CHAR86} on pages 130--131

\huge
		\begin{itemize}

	\vfill
		\item 
	Let $G$ be a nontrivial connected graph with $V(G) = \{v_{1},
        v_{2}, \ldots, v_{p}\}$.  

	\vfill
		\item 
	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}$.

	\vfill
		
		\item 
        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{itemize}
\Huge
\newpage

	\item Example: 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=3in}}
        \caption{A Planar embedding of a graph}
        \label{fig:edmonds}
        \end{figure}

	\item  From these permutations we can obtain:
		\begin{itemize}
		\item the edges of the graph.
		\item the number of regions of the graph.
		\item the edge boundaries for each region.
		\end{itemize}

\newpage

 	\item 	
	The second author in \cite{lr:cnopg} developed a computer program
        to take a graph and generate all vertex permutation schemes.  It
        then would determine the regions of the resulting embedding
        and thereby determine if a given graph had a planar embedding,
        and if so, what its regions were.  

	\item 
	The code for this program
        can be found in \cite{lovegrove:masters}.

	\end{itemize}
	
\newpage
\noindent
V. Depth First Search (DFS) with Branch and Bound

        \vspace{0.25in}
	 Used to solve Discrete Optimization Problems (typically
		formulated as a tree-search problem)
        \vspace{0.25in}

	\begin{itemize}
	\item DFS begins by expanding the initial vertex and generating
		its successors

        \vspace{0.25in}
	\item In each subsequent step DFS expands one of the most
	recently generated vertices.

        \vspace{0.25in}
	\item If a stopping condition is reached, backtracking occurs.

        \vspace{0.25in}
	\item Stopping Conditions include:
		\begin{itemize}
		\item A vertex has no successors.
		\item This branch cannot lead to any good solution 
			(too expensive).
		\end{itemize}
	\end{itemize}

\newpage
\noindent
VI. The Proposed Algorithm
	\begin{itemize}
	\item Begin with the vertex set
        \vspace{0.25in}
	\item Add edges while the resulting partial graph is planar.
		(this uses the rotational embedding scheme)
        \vspace{0.25in}
	\item For all the rest of the edges... 
		\begin{itemize}
		\item lay them down one at a time.
		\item creating a vertex of degree 4 where crossings
			occur (thereby keeping the graph planar)
		\end{itemize}
        \vspace{0.25in}

	\item Now backtrack to make different decions (where to
			put the crossing)
	\end{itemize}

\newpage
	Example: $K_{5}$

        \centerline{\psfig{figure=k5-a.ps,height=5in}}
\newpage
	Example: $K_{5}$

        \centerline{\psfig{figure=k5-b.ps,height=5in}}
\newpage
	Example: $K_{6}$

        \centerline{\psfig{figure=k6-a.ps,height=5in}}
\newpage
	Example: $K_{6}$

        \centerline{\psfig{figure=k6-b.ps,height=5in}}
\newpage
\noindent
VII. Future Work

	\begin{itemize}
	\item Implementation.
               \vspace{0.25in}
	\item Verification.
               \vspace{0.25in}
	\item New Results.
               \vspace{0.25in}
	\item Parallelization.
	\end{itemize}
\newpage
%\normalsize
\Large
\baselineskip=12pt
\parskip=0pt
\parsep=0pt
\itemsep=0pt
\bibliography{/staff/fredh/papers/bibdir/xing,/staff/fredh/papers/bibdir/fredh}

\end{document}
