% 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 minimum crossing number of a graph. We begin with the vertex set and add edges by selecting every legal option for creating a crossing or not. After each edge is added we determine if the resulting partial graph is planar. We continue adding edges until either all edges have been added or we reach a point where the graph cannot be completed as started. At this point we backtrack to see if the graph can be drawn with fewer crossings by selecting other options when adding edges. \noindent {\bf keywords:} Crossing Number, Algorithm \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~\cite{leighton83:ciivlsi}. 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 the general solutions. 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. Because of the difficulty of this problem, work turned away from finding the minimum crossing number of a graph to sub-problems and other related problems. With regard to the sub-problems, there has been work on product graphs ranging from the product of $C_{n}$ and graphs of order four~\cite{br80:otcnopocagoof} to $C_{3} \times C_{n}$~\cite{rb78:tcnoc3xcn}, $C_{4} \times C_{4}$~\cite{dr95:tcnoc4xc4}, $C_{5} \times C_{5}$~\cite{rt95:iocsatcnoc5xc5}, and $C_{5} \times C_{n}$~\cite{krs96:tcnoc5xcn}. There has also been work in the area of bipartite graphs with the results of $K_{3,n}$~\cite{rs96:tcnok3nias}, $K_{5,n}$~\cite{kleitman71:tcnok5n}, and the torroidal crossing number of $K_{m,n}$\cite{gj69:ttcnokmn} having been found. In 1991 Beinstock published work \cite{bienstock91:sphcnp} relating the crossing number of a graph to the arrangement of pseudolines,a topic well studied by combinatorialists. There have also been several related problems that have been studied over the years. Some of these range from the rectilinear crossing problem~\cite{GUY72,thomassen88:rdog,th96:apsoaffmormcp} to the maximum crossing number of a graph or subgraph~\cite{ghprs:citcg,hks73:tgwahcn} 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 gives us the foundation for 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. 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 given 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}. 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 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 of the vertices 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}[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 From permutation $\pi_{2}$ determine which vertex follows 1; it is 4. Therefore the second edge is (2,4). \item From permutation $\pi_{4}$ determine which vertex follows 2; it is 1. Therefore the third edge is (4,1). \item From permutation $\pi_{1}$ determine which vertex follows 4; it is 2. This yields edge (1,2) which was the original edge, so we are finished. \end{list} } \noindent The region we considered is bounded by the edges (1,2), (2,4), and (4,1). The other regions and associated edges can be found in a similar manner. The important thing to note 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 of the regions and determine the genus of the surface on which the graph is embedded. 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 has motivated us to keep track of regions in the construction of a graph drawing, which is the basis for our proposed algorithm presented in Section~\ref{sec:pa}. \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 cost of 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 without covering 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 map the solution space from the crossing number problem onto a tree and search for the minimum crossing number with a DFS with branch-and-bound. The root of our tree corresponds to the vertex set. The root has $|E|$ (the number of edges) branches coming out of it. Each branch corresponds to the first edge that is added to the graph. The next level of the tree has $|E|-1$ branches coming out of each node. The tree is $|E|$ levels deep, and the path to each leaf corresponds to a unique permutation ordering for the edges. We begin by selecting edge $(i,j)$. We use Euler's Formula to determine if the edge can be added from vertex $i$ to vertex $j$ without any crossings. (We do this by keeping track of the number of regions in the graph as it is constructed.) If so, we add the edge and select the next edge. If not, we choose an edge that has already been added to cross. (This may be the only edge crossed, or the first edge in a long list of edges to be crossed). Once we decide that edge $(i,j)$ is to cross edge $(k,l)$ we create a new vertex $m$, remove edge $(k,l)$, add partial edges $(k,m)$, $(m,l)$, and $(i,m)$, and then draw edge $(m,j)$ in the same fashion. When drawing an edge, we remember that an edge cannot cross itself, that no pair of adjacent edges cross, and that two edges cross at most once. We also keep track of all partial edges and remember that they are actually {\it part} of an edge. In the scenario described in the previous paragraph, we would have to remember that edge $(i,m)$ is part of edge $(i,j)$. Let us demonstrate the algorithm with $K_{5}$ as our example. $K_{5}$ has 10 edges. The first 9 are added directly without crossing another edge. This partial graph is shown in Figure~\ref{fig:k5b}. When the last edge is considered, Euler's Formula indicates that the resulting graph cannot be embedded on the plane. \begin{figure}[bht] \vspace*{0.1in} \centerline{\psfig{figure=k5-b.ps,height=2in}} \caption{First 9 edges of $K_{5}$ with no crossings} \label{fig:k5b} \end{figure} Therefore, we must add the edge $(i,j)$ with at least one crossing. At this stage we select edge $(k,l)$ to cross, insert vertex $m$, remove edge $(k,l)$, and add partial edges $(k,m)$, $(m,l)$, and $(i,m)$. The graph is as shown in Figure~\ref{fig:k5c}. Once these partial edges have been drawn the algorithm tries to draw the rest of edge $(i,j)$ without any crossings and succeeds. Figure~\ref{fig:k5d} shows this drawing of $K_{5}$ with one crossing. \begin{figure}[h] \vspace*{0.1in} \centerline{\psfig{figure=k5-c.ps,height=2in}} \caption{The first part of the last edge is drawn for $K_{5}$} \label{fig:k5c} \end{figure} \begin{figure}[h] \vspace*{0.1in} \centerline{\psfig{figure=k5-d.ps,height=2in}} \caption{One drawing of $K_{5}$ with 1 crossing at m} \label{fig:k5d} \end{figure} The algorithm then backtracks with a new bound of one crossing. It will then back up through the rest of the tree and try all other parts of the tree. However, once the algorithm has determined that it cannot add an edge without any crossings, it will not try any further down that branch since the best drawing so far has one crossing. It will finish when it has exhausted all possibilities. In the case of $K_{5}$, no possibility will result in a drawing with zero crossings. \section{Conclusions and Future Work}\label{sec:fw} We have presented a proposed algorithm for calculating the minimum crossing number of a graph. This could also be extended to finding the maximum crossing number by making minor modifications to the search algorithm. We could also find all possible drawings with the minimum crossing number, or we could remove the bound and enumerate all possible drawings of a graph. The first step in the future work is 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 matters in reaching the correct answer more quickly. The order may be important for graphs in general, but it may not for certain classifications (such as $K_{n}$). Once that has been determined, we would like to calculate the crossing number for several families which are important in 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 DFS branch-and-bound algorithms can achieve super-linear speedup. %\section*{Acknowledgments} % We would like to acknowledge the referees comments, whose % inclusion have helped to make this a better paper. \baselineskip=12pt \parskip=0pt \parsep=0pt \itemsep=0pt \bibliography{/staff/fredh/papers/bibdir/xing,/staff/fredh/papers/bibdir/fredh} \end{document}