%%%%%%%%%%%%%%%%%%%%%%%%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 Minimum 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 capabilities increase. Unfortunately the applications are 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 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 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} we 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} \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 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{The First Sequential Algorithm}\label{sec:sequential} When we began studying this problem we were amazed that we could not find a single citation in the literature that discussed how to solve this problem algorithmically. Several heuristics and conjectures were found \cite{eg:cnog,gj83:cninpc,GUY72,turan:1977}, but there were no algorithms. Therefore, we began to work on a sequential algorithm for computing the minimum crossing number of a graph. This past year one of us presented a proposed algorithm for sequentially calculating the minimum crossing number of a graph \cite{hh96:apafctmcnoag}. In this algorithm we mapped the solution space of 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 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 availability. 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 algorithm 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-studied family. Secondly, it is one of the few families with a conjectured formula for the minimum crossing number. For complete graphs of size 10 and less, a simple formula provides the minimum crossing number \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 its minimum crossing number, and that of larger members of the family, in parallel. \begin{table}[h] \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}[h] \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 consider dynamic partitioning of the workload. \section{Conclusions and Future Work}\label{sec:fw} We have presented a parallel algorithm for calculating the minimum crossing number of a graph. This has been 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 that 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 effectively. 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 the exact solution of 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%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%