
%%%%%%%%%%%%%%%%%%%%%%%%CUT HERE%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% This is proc209.tex, an example file for use with the SIAM LaTeX 2.09
% Proceedings Series macros. 
% Please take the time to read the following comments, as they describe
% how to use these macros. This file can be composed and printed out for
% use as sample output.

% Any comments or questions regarding these macros should be directed to:
%
%                 Corey Gray
%                 SIAM
%                 3600 University City Science Center
%                 Philadelphia, PA 19104-2688
%                 USA
%                 Telephone: (215) 382-9800
%                 Fax: (215) 386-7999
%                 e-mail: gray@siam.org


% This file is to be used as an example for style only. It should not be read
% for content.

%%%%%%%%%%%%%%% PLEASE NOTE THE FOLLOWING STYLE RESTRICTIONS %%%%%%%%%%%%%%%

%%  1. There are no new tags.  Existing LaTeX tags have been formatted to
%%     match the Proceedings series style.    
%%
%%  2. You must use \cite in the text to mark your reference citations and 
%%     \bibitem in the listing of references at the end of your chapter. See
%%     the examples in the following file. The file siamproc.bst has been 
%%     included for use with BiBTeX. 
%% 
%%  3. This macro is set up for three levels of headings (\section, 
%%     \subsection, and \subsubsection). The macro will automatically number 
%%     the headings for you.
%%
%%  4. Theorems, Lemmas, Definitions, etc. are to be double-numbered, 
%%     indicating the section and the occurrence of that element
%%     within that section. (For example, the first theorem in the second
%%     section would be numbered 2.1. The macro will 
%%     automatically do the numbering for you.
%%
%%  5. Proofs are handled with the commands \begin{proof}\end{proof}.
%%     If you wish to use an end of proof box, use \qed preceding \end{proof}.
%%     The example uses one. It is not required.
%%
%%  6. Figures, equations, and tables must be single-numbered. All equation
%%     numbers are to be on the left. Figure captions should be placed under
%%     the figures they pertain to. Table captions should be placed above 
%%     the tables. Use existing LaTeX tags for these elements. Numbering of 
%%     these elements will be done automatically. 
%%   
%%  7. Grant information and author affiliations.
%%     This information is included in the file with the two commands,
%%     \thanks and \footnotemark []. (See example). The \thanks command 
%%     produces a footnote for the title or author, and places the 
%%     appropriate footnote symbol with the title or author and at the
%%     bottom of the page. The \footnotemark [] command allows the use of
%%     duplicate footnote symbols. This macro follows the normal LaTeX order 
%%     of footnote symbols. Below is a list of these symbols, and their 
%%     corresponding footnotemark:
%%
%%      asterisk                \footnotemark[1]
%%      single-dagger           \footnotemark[2]
%%      double-dagger           \footnotemark[3]
%%      section sign            \footnotemark[4]
%%      paragraph               \footnotemark[5]
%%      parallel                \footnotemark[6]
%%      double asterisk         \footnotemark[7]
%%      double single-dagger    \footnotemark[8]
%%      double double-dagger    \footnotemark[9]   
%%
%%    The following general rules for grants and affiliations apply:
%%      a) If there is a single grant for the paper, then the grant 
%%         information should be footnoted to the title.
%%      b) If there is more than one grant, include the grant information
%%         with each author's affiliation.
%%      c) If there are different grants for the paper but the authors share
%%         the same affiliation, footnote the grant information to the title.
%%         For example, The work of the first author was supported by xyz.
%%         The work of the second author was supported by abc. And so on.
%%      d) For authors sharing the same affiliation, use \thanks for the
%%         first author with that affiliation and the appropriate
%%         \footnotemark[] (from the list above) for all subsequent authors
%%         with that affiliation.
%%
%%
%%
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%-
%%%


\documentstyle[leqno,twoside,11pt,proc209]{article} %You must set up your
                                              %\documentstyle line like this.

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

\cleardoublepage
\pagestyle{headings}

\title{Parallel Computation \\ of the Minimal Crossing Number of a Graph}
\author{
Umid Tadjiev
\thanks{Department of Computer Science, University of Nevada, Reno NV
89557, tadjiev@cs.unr.edu, fredh@cs.unr.edu}
\and 
Frederick C. Harris, Jr.
\footnotemark[1]
}
\date{}
\maketitle

\pagenumbering{arabic}

\begin{abstract}
        Determining the crossing number of a graph is an important
        problem with applications in areas such as circuit design
        and network configuration.
        In this paper we present the first parallel algorithm for
        solving this combinatorial optimization problem.
        This branch-and-bound algorithm, which adds and deletes
        crossings in an organized fashion,
        presents us with the opportunity to verify many
        conjectures which are decades old,
        as well as pursuing future work in efficient circuit
        design.
\end{abstract}

\section{Introduction}

	Optimal circuit layout and network design are two problems that
	are becoming more important as the number of computers grows
	rapidly and their capabilites increase.   Unfortunately the
	application is obvious but the theory available to help solve
	the problem is quite deficient.  Determining the crossing
	number of a graph is a problem whose solution could improve the
	state of the theory in this important application area.  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:sequential} present the first sequential
	algorithm for the problem.  The parallel algorithm is discussed
	in Section~\ref{sec:parallel} and 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{Definition}
               % \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}
	\end{Definition}


\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{Definition}
        %\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}
	\end{Definition}

        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 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.

        A computer program to generate all vertex permutation schemes 
	for a graph was developed in \cite{lr:cnopg}.
        This program 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 Sections~\ref{sec:sequential} and \ref{sec:parallel}.

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

        If the solution space of a 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{The First Sequential Algorithm}\label{sec:sequential}

	Amazingly we have been unable to find any citation in the
	literature that discusses how to solve this problem
	algorithmically.  It was not until this past year that one of
	us presented a proposed algorithm for sequentially calculating
	the minimal crossing number of a graph in
	\cite{hh96:apafctmcnoag} that one has been available.

        In this algorithm we mapped the solution space from the 
	crossing number problem onto a tree and then searched
        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=1.8in}}
        \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
        \begin{figure}
        \centerline{\psfig{figure=k5-c.ps,height=1.8in}}
        \caption{Beginning to lay down the alst edge for $K_{5}$}
        \label{fig:k5c}
        \end{figure}
        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}.
        \begin{figure}
        \centerline{\psfig{figure=k5-d.ps,height=1.8in}}
        \caption{One drawing of $K_{5}$ with 1 crossing}
        \label{fig:k5d}
        \end{figure}
        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.


\section{A Parallel Algorithm and Implementation}\label{sec:parallel}

	The parallel algorithm for this preliminary work was very
	straightforward.  In order to obtain some initial results we
	did a basic static partitioning of the search tree among the
	$p$ processors in our parallel machine.  This method, along
	with its benefits and drawbacks, is discussed in detail in
	\cite{kggk:book}. We figured we would attempt this first and
	see if it was reasonable, and then modify it later to more
	dynamic methods after the feasibility was determined.

	The implementation of this algorithm was developed on and run
	on a network of Pentium 133 machines running Linux.  This
	network of machines was linked together into a parallel cluster
	with PVM \cite{PVM:book} using a host-node programming style.
	This configuration was chosen for its ease of use and
	availablilty.  In the future we wish to modify the
	implementation to have dynamic partitioning of the search space
	and target a new multiprocessor shared memory machine that has
	just become available.

	For evaluation of this alorithm and its implementation we
	decided to use the family of complete graphs, denoted $K_{n}$,
	as our test cases.  This family was selected for a few
	reasons.  First it is one of the few families of graphs where
	there are some known answers since it is well-understood
	family.  Secondly, it is one of the few families with a
	conjectured formula for the minimal crossing number.
	For graphs of size 10 and less, a simple formula provides the
	minimal crossing number for complete graphs \cite{GUY72}:

	\[ \nu (K_{n}) = \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}
        \]

	This formula, which is conjectured by Richard Guy to be the
	exact answer for all n \cite{GUY72}, provided a ball park for
	an initial bounds when doing our branch-and-bound search.  
	The results of the sequential and
	parallel versions are shown in Table~\ref{tab:timings}.  This
	basically shows that the computation times for $K_{6}$ and
	$K_{7}$ are so small that we do not have to worry about the
	parallel implementation; however, $K_{8}$ has a computation time
	that makes it very desirable to compute this, and larger members
	of the family, in parallel.

	\begin{table}
        \caption{Computation time (in seconds) for $K_{6}$ - $K_{8}$
	with $p$ processors}\label{tab:timings}
	\begin{center}
	\begin{tabular}{c|r|r|r|}\cline{2-4}
		%& \multicolumn{3}{c|}{Processors} \\ \cline{2-4}
		& $p = 1$	& $p = 2$	& $p = 4$	\\ \hline
		%& 1	& 2	& 4	\\ \hline
	\multicolumn{1}{|c|}{$K_{6}$}	&0 	&0 	&1	\\
	\multicolumn{1}{|c|}{$K_{7}$}	&8	&4	&3	\\
	\multicolumn{1}{|c|}{$K_{8}$}	&12230	&6251	&3794	\\ \hline
	\end{tabular}
	\end{center}
	\end{table}

	From this point on we dealt with $K_{8}$ almost exclusively. 
	We will attack $K_{9}$ and others in this family when we have
	finished some optimization that we will discuss in Section 
	\ref{sec:fw}.  The numbers just
	presented for $K_{8}$ yield the speedup given in
	Figure~\ref{fig:speedup} and an efficiency as given in
	Table~\ref{tab:efficiency}.

	\begin{figure}
	\begin{center}
	\input{plot}
	\end{center}
	\caption{Speedup for $K_{8}$ as a function of $p$ processors}
	\label{fig:speedup}
	\end{figure}

	\begin{table}
        \caption{Efficiency for $K_{8}$ as a function of $p$ processors}
	\label{tab:efficiency}
	\begin{center}
	\begin{tabular}{c|r|r|r|}\cline{2-4}
		%& \multicolumn{3}{c|}{Processors} \\ \cline{2-4}
		& $p = 1$	& $p = 2$	& $p = 4$	\\ \hline
	\multicolumn{1}{|c|}{$K_{8}$}	&1.0	&0.9782	&0.8058	\\ \hline
	\end{tabular}
	\end{center}
	\end{table}

	The interesting thing to note is the time for $K_{8}$ with four
	processors.  For this computation two of the slaves finished 
	in almost identical times of about 3050 seconds, while the other 
	two were both around the final result of 3794 seconds.  This 
	detail points out one of the major problems with static
	partitioning in tree search algorithms, and that is lack of 
	balanced workloads.  For this reason we must look towards a
	dynamic partitioning of the workload.

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

        We have presented a parallel algorithm for calculating the
        minimal crossing number of a graph.  This has built upon 
	the proposed sequential algorithm we presented in
	\cite{hh96:apafctmcnoag}.  We have implemented this algorithm,
	and shown its capabilites by comparing the sequential and the 
	parallel versions on some of the initial members of the family 
	of Complete Graphs ($K_{7}$ and $K_{8}$) that are not trivial.

	We see this work continuing in various different ways.  First
	we would like to construct a package which will be able to
	automatically draw the resulting graphs which we can compute.
	Secondly we would like to examine the computational method used
	in the sequential method and see if there are portions that can 
	be improved, since this could improve the parallel version 
	dramatically.  This would range from looking at a best first
	search with a dynamic queue of work as Quinn and Deo presented
	in \cite{qd85:ubspbbbba} to looking at various graph theoretic
	ways to legally prune the tree more than we currently are.

	Then we would like to go back to calculate the crossing 
	number for several families which are very important when 
	looking at circuit design, such as the rest of $K_{n}$, 
	$K_{(m,n)}$, and various others.  We are hoping that at around
	$K_{12}$ we will be able to show a counter-example (as we did
	with the rectilinear crossing problem 
	\cite{th96:apsoaffmormcp}) to the conjecture proposed by 
	Richard Guy \cite{GUY72} many years ago as to the exact 
	solution to this problem.  


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

\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%CUT HERE%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
