A Time-Saving Region Restriction for Calculating the MCN of Kn Judith R. Fredrickson, Bei Yuan, Frederick C. Harris, Jr. Department of Computer Science and Engineering University of Nevada Reno, NV 89557 {fredrick, bei, fredh}@cs.unr.edu Abstract 1. Introduction and History The year was 1944, the location Hungary. Paul Turán documented a personal experience with the following description [Char96]: We worked near Budapest, in a brick factory. There were some kilns where the bricks were made and some open storage yards where the bricks were stored. All the kilns were connected by rail with all the storage yards. The bricks were carried on small wheeled trucks to the storage yards. All we had to do was to put the bricks on the trucks at the kilns, push the trucks to the storage yards, and unload them there. We had a reasonable piece rate for the trucks, and the work itself was not difficult; the trouble was only at the crossings. The trucks generally jumped the rails there, and the bricks fell out of them; in short this caused a lot of trouble and loss of time which was precious to all of us. We were all sweating and cursing at such occasions, I too; but nolens volens the idea occurred to me that this loss of time could have been minimized if the number of crossings of the rails had been minimized. But what is the minimum number of crossings? Turán had conceptualized and documented the crossing number problem. Known as Turán’s Brick Factory Problem, Turán’s query is considered the birth of the crossing number problem. Over the years, many have studied this easily stated problem but little is known about general solutions. Garey and Johnson [GJ83] proved that finding the minimum crossing number of a graph was NP- complete. Because of the difficulty of this problem, work turned away from finding the crossing number of a graph to sub-problems and other related works. Pach and Toth [PT00b] is a good resource for an overview of references and current open problems on crossing numbers for various graph families. An interesting discussion of the many different interpretations of a ‘graph drawing’ can be found in [PT00a]. Almost twenty years before the NP-complete proof of the crossing number problem Guy initiated the pursuit of the crossing number of the complete graph Kn [Guy60]. A graph with n vertices is complete if every two of its vertices are adjacent. Our current work joins in Guy’s pursuit. We pursue complete graphs as they are a well studied graph family. Some known answers exist upon which to test our theories. We employ the algorithm proposed by Harris and Harris in [HH96]. The algorithm uses an exhaustive search to find the Minimum Crossing Number (MCN) of a graph. As graph size increases, exhaustive searches can become computationally intensive—taking months or even years to complete on a single processor. Using a medium to large Beowulf cluster and a parallel queuing system, along with an updated definition of a good graph we have efficiently solved the MCN of a complete graph for a number of vertices less than nine. Parallel implementation of the Harris and Harris algorithm has gone through several iterations and improvements in recent times [TH97, T98, M03, YFMH04]. Those interested in more detail are directed to these references. By harnessing the power of computer clusters, and tightening the definition of a good graph drawing from a region perspective, the MCN problem may be solved for larger graphs. The remainder of this paper is laid out as follows: Section 2 presents notation and definitions, background information on crossing numbers for complete graphs, explanation of the Harris and Harris algorithm, and brief coverage of the parallel queuing system environment employed. Section 3 describes the new region restriction we use to aid in greatly reducing the search space size along with results. Section 4 contains our conclusions and current and future work including a proposed radical region restriction. 2 Background Work 2.1 Terminology and Definitions We now informally define some terms from graph theory which will be used in the rest of the paper. These definitions are based on [Char96]. For our purposes, a compact-orientable 2-manifold, or simply a surface, may be thought of as a sphere or a sphere with some number of ‘handles’ placed on it. Definition 1.1 The genus of a surface S is the number of handles on the surface. Definition 1.2 The genus gen(G) of a graph G is the smallest genus of all surfaces on which G can be embedded. Definition 1.3 A graph G is embeddable on a surface S if it can be drawn on S such that any two edges that intersect do so only at a vertex of G mutually incident with them. Definition 1.4 A graph is a planar graph if it can be embedded on the plane. Definition 1.5 A planar graph that is embedded on the plane is called a plane graph. Definition 1.6 A region of the plane graph G is a connected portion of the plane remaining after all curves and points corresponding to edges and vertices of G have been deleted. Definition 1.7 A region is called a 2-cell region if any simple closed curve in that region can be continuously deformed or contracted in that region to a single point. Definition 1.8 An embedding is a 2-cell embedding if all the regions in an embedding are 2-cell. Definition 1.9 A good drawing of a graph G is one with the following properties: * adjacent edges never cross * two nonadjacent edges cross at most once * no edge crosses itself. * no more than two edges cross at a point. * the (open) arc in the plane corresponding to an edge of the graph contains no vertex of the graph. Definition 1.10 The minimum crossing number (MCN), ?(G), of a graph is the minimum number of edge crossings among all the good drawings of G in the plane. 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 Euler’s Formula: Let G be a connected graph with n vertices and m edges with a 2-cell embedding on the surface of genus g and having r regions, then n – m + r = 2 – 2g The definitions related to embeddings and Euler’s Formula are vital to the Harris and Harris algorithm as it employs Edmonds’ Rotational Embedding Scheme. We discuss both in section 2.3. 2.2 Minimum Crossing Number As stated we are concentrating on the MCN of Kn. First, we differentiate between the two general categories of crossing numbers for graphs. The MCN, ?(G), allows for edges that are nonlinear. Another category of crossing numbers is the rectilinear crossing number, which is defined similarly but with the restriction that each edge is a straight line segment. For graphs of size 10 and less, a simple formula provides the minimal crossing number for complete graphs [G72]: (1) The rectilinear crossing number also holds for this formula, with the notable exception of graphs with 8 vertices. For K8, the crossing number is 18; while for rectilinear graphs the crossing number is 19. As the crossing problem increases in size (11 vertices or more), a different formula appears to hold true for the rectilinear case: (2) Guy [G72] proposed this formula is 1972, and conjectured that this formula was an equality. The equality conjecture was shown to be false when Thorpe and Harris [TH96] generated a rectilinear drawing of K12 with 155 crossings. Recent work by Brodsky et al. [BDG01] and Aichholzer et al. [AAK01] give us the rectilinear crossing number for K10 = 62 and [AAK02] has determined the rectilinear crossing number for K11 = 102 and K12 = 153. Also in 1972, Guy [Guy72] conjectured that equation (1) holds true for all n. To date this conjecture still stands It is anticipated that divergence around n of size 12 or 13 is possible as was seen in the rectilinear case [***Guy talk***]. 2.3 An Overview of the Algorithm Used As noted we employ an exhaustive search, branch and bound, algorithm proposed by [HH96]. An overview of it is presented to allow for understanding of the region restriction presented in section 3. 2.3.1 Edmonds’ Rotational Embedding Scheme We start with a look at the Rotational Embedding Scheme, first formally introduced by Edmonds [E60] in 1960 and then discussed in detail by Youngs [Y63] a few years later. The following is the formal statement of the Rotational Embedding Scheme as presented in [CL96] on pages 196-197. Use this updated statement of the Scheme as some notation has changed. %\begin{quote} Let G be a nontrivial connected graph with $V(G) = \{v_{1}, v_{2}, $\ldots, v_{n}\}$. For each 2-cell embedding of G on a surface there exists a unique n- tuple $(\pi_{1}, \pi_{2}, \ldots, \pi_{p})$, where for $i = 1, 2,$ $\ldots, n$, $\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 n-tuple $(\pi_{1}, \pi_{2}, \ldots, \pi_{n})$, there exists a 2-cell embedding of G on some surface such that for $i = 1, 2, \ldots,n$ the subscripts adjacent to $v_{i}$ and in the counterclockwise order about $v_{i}$, are given by $\pi_{i}$. %\end{quote} pull in the rest of of Rot . Emb discussion from [TH96] 2.3.2 The Harris and Harris Algorithm In this algorithm the solution space of the crossing number problem is mapped onto a tree and then searched for the minimum crossing number with a branch and bound depth first search (DFS). A DFS 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. Branch and bound allows us to change one small part of the DFS algorithm. When the cost to get to a vertex v exceeds the current optimal solution, we tell the DFS algorithm not to traverse the subtree having vertex v as its root. This saves us from having to cover a section of the search space that is guaranteed to cost more than the current optimal solution. 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 2.3.1. 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 root of the tree has a branch for each possible planar 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 vertex i to vertex j). The first option we have is which one of the k regions that vertex 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 vertex i to the cross vertex and then try to lay the edge from the cross vertex to vertex 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 K5 as our example. In Figure 2 {fig:k5b} we have the vertex set for the graph with all the edges added to the graph while it can still remain planar. [TH96] Figure 2 Figure 2 Planar portion of K5 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 3{fig:k5c}. We then find out if 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 4{fig:k5d}. The algorithm then backtracks and tries the other regions i is adjacent to and finds out that there are multiple ways to draw K5 with one crossing, but none with zero crossings. [TH96] figure 3 Figure 3 Beginning to lay down an edge for K5 [TH96] figure 4 Figure 4 One drawing of K5 with one crossing 3 Restricting a Good Drawing Through Region Analysis Recall from section 2.1 the definition of a good drawing: Definition 1.9 A good drawing of a graph G is one with the following properties: * adjacent edges never cross * two nonadjacent edges cross at most once * no edge crosses itself. * no more than two edges cross at a point. * the (open) arc in the plane corresponding to an edge of the graph contains no vertex of the graph. Figure 3.1 shows four edge placements from vertex u to v that will be generated based on Definition 1.9. Figure 3.1(a) and (b) both illustrate placement of edge uv with generation of one crossing. Notice that Figure 3.1 (c) and (d) generate four and five extra crossings, respectively. Both (c) and (d) satisfy Definition 1.9 but upon examination we see that the drawing in Figure 3.1(a) crosses the same edge from region R1 to region R2 while laying down the first edge segment emanating from vertex u. Recall that each R1 edge not incident to vertex u will be used in generating all valid uv edges, so we are assured that the edge placement shown in Figure 3.1(a) will be generated. Thus the drawings in Figure 3.1(c) and (d), though valid, will not aid in producing a complete graph with a minimum number of crossings. Figure 3.1 Good Graph Drawings With this observation we introduce a modification of Definition 1.9 to include a region restriction. Definition A restricted good drawing of a graph G is one with the following properties: * adjacent edges never cross * two nonadjacent edges cross at most once * no edge crosses itself * no more than two edges cross at a point * the (open) arc in the plane corresponding to an edge of the graph contains no vertex of the graph * an edge, emanating from any vertex u of graph G, that crosses a region of G is then restricted from entering any region having vertex u on its boundary This added restriction eliminates both graphs in Figures 3.1 (c) and (d) from being generated. Figure 3.2 shows the laying down of the six initial edge segments emanating from vertex u in laying of all valid edges from u to all other nonadjacent vertices. For any of the edges from u to v of G, the edges will be restricted from entering regions R1, R6 and R5 after this initial segment placement. With each additional set of edge segments placed the relevant regions will join the list of restricted regions for any given edge. Figure 3.2 Initial edge segments from vertex u to other nonadjacent vertices Modification to the graph generation algorithm was minimal. Whenever an edge segment is laid down, its initiating vertex is used to add to, or create, a list of restricted regions for that edge. 3.1 Results Table 3.1 shows a comparison of the number of partial edges, or jobs, generated when building Kn for 5 n 8 with and without the restricted good graph. Tests were run on 4 parallel processors. For all n in the table, the restricted good graph tests generated graph(s) with the true minimum crossing number. Vertices (n) ?(Kn) Good Graph Restricted Good Graph 5 1 3 3 6 3 203 71 7 9 1,498,775 25,109 8 18 * 46,697,854 Table 3.1 Restricted versus Good Graph Jobs Processed A substantial search space reduction has been introduced as can been seen in comparing results for n = 7. The search space is reduced by nearly a factor of 60. Results were achieved for n = 8 that were unachievable without the restriction. Using the good graph definition alone we were unable to generate any complete graphs for n = 8 after over a week of runtime. With the restricted good graph we fully processed all jobs in under four hours. This time reduced to just over 2 hours when running on six processors. Tests were run on K9 and results for the MCN were not achieved. Tighter restrictions on the search space will be needed. 4. Conclusions We have presented a tightening of the definition of a good graph drawing for use with a parallel, branch and bound, exhaustive search algorithm for finding the crossing number of complete graphs. The new definition examines graphs not only as sets of vertices and edges but in terms of a set of regions. Implementation of the region restriction on the laying down of an edge during graph building has greatly reduced the search space of this problem for n less than 9. This initial step in the direction of region examination for search space reduction is promising as it has prompted new questions related to even tighter region restrictions to be explored. 4.1 Future Work The success of the restricted good graph for n less than 9 has prompted a further restriction that is currently an open question. The ‘radical region restriction’ is a greedy edge placement based on the analysis of the regions from one vertex to another. The question we pose: If when laying down all edges from vertex u to vertex v of graph G is it okay to be greedy and only generate those edges that are of the minimum region separation from u to v? For example, Figure 4.1 shows four of the ten possible uv edge placements for the given graph. Figure 4.1 (a) and (b) are the only two possible uv edge placements that have the minimum number of regions (in this case two) separating u and v. The minimum number of separating regions, being two, indicates that only one crossing will be generated in each of these cases. Figure 4.1 (c) and (d) show two other uv edge placements of the remaining eight, each of which separates u and v by three regions. A three region separation will introduce two crossings. Is it okay to generate the two ‘shortest path’ edges and ignore the rest? In other words: Is greedy good? Another issue that has bearing on this question and our graph generation in general is that of order. Does it matter in which order the edges are laid down? If order doesn’t matter we will be able to greatly prune the search tree of possible edge placements. We look to generate complete sets of MCN graphs for small n and separate the results into non-isomorphic families. At this point region restrictions and order questions can be tested to see if any of the families are lost. Once we know that non-isomorphic families are not missing we can fine tune a tree pruning method that will not overlook the minimum crossing number for a graph. Figure 4.1 Edge Placement for edge uv Once we know that we are locating the MCN for Kn with our pruning methods intact we hope we can generate a counterexample to the conjecture , equation (1), posed by Guy [Guy70] many years ago as the exact solution of this problem. It is anticipated that divergence may take place around n = 12 as it did in the rectilinear case[TH96]. Another avenue of exploration is trying to generate the MCN of Kn using the non-isomorphic MCN graph families of Kn-1 as feeder graphs for Kn MCN graph generation. A construction based method of larger n may be attainable in the future. 5. References [AAK01] O. Aichholzer, F. Aurenhammer, H. Krasser, Enumerating order types for small point sets with applications. In Proc. 17th Ann. ACM Symp. Computational Geometry, Medford, MA, 2001, 11-18. [AAK02] O. Aichholzer, F. Aurenhammer, H. Krasser, On the crossing number of complete graphs. In Proc. 18th Annual ACM Symposium on Computational Geometry, ACM Press, 2002, 19-24. [Bie92] D. Bienstock, Some provably hard crossing number problems. Discrete & Computational Geometry 6 (1991), 443-459 [BDG01] A. Brodsky, S. Durocher, E. Gether, The rectilinear crossing number of K10 is 62. The Electronic J. of Combinatorics 8 (2001), Research Paper 23. [CL96] G, Chartrand and L. Lesniak, Graphs & Digraphs, 3rd edition. Chapman & hall/CRC, Boca Raton, FL, 1996 [E60] J. Edmonds, A combinatorial representation for polyhedral surfaces, Notices Amer. Math. Soc., 7 (1960, p. 646. [GJ83] M. R. Garey and D. S. Johnson. Crossing number is NP-complete. SIAM Journal of Algebraic and Discrete Methods, 4:312-316, 1983. [Guy60] R. K. Guy. A combinatorial problem. Nabla (Bulletin of the Malayan Mathematical Society), 7:68-72, 1960. [Guy72] R. K. Guy. Crossing numbers of graphs. In Graph theory and applications (Proc. Conf., Western Michigan Univ., pages 111- 124. Lecture Notes in Math., Vol. 303, Springer, Berlin, 1972. [HH62] F. Harary, A. Hill, On the number of crossings in a complete graph. In Proc. Edinburgh Math. Society (2) 13, 1962, pages 333- 338. [HH96] F. C. Harris, Jr. and C. R. Harris, A proposed algorithm for calculating the minimum crossing number of a graph, in Proceedings of the Eighth Quadrennial International Conference on Graph Theory, Combinatorics, Algorithms, and Applications, Y. Alavi, A. J. Schwenk, and R. L. Graham, eds., Kalamazoo, Michigan, June 1996, Western Michigan University. [M03] S. C. Martin. A parallel queuing system for computationally intensive problems on medium to large Beowulf clusters. Master’s Thesis, University of Nevada, Reno, NV 89557, December 2003. [PT00a] J. Pach, G. Toth. Which crossing number is it, anyway? J. Combinatorial Theory B 80, 2000, pages 225-246. [PT00b] J. Pach, G. Toth. Thirteen problems on crossing numbers. Geombinatorics 9, 2000, pages 225-246. [T98] U. Tadjiev. Parallel Computation and Graphical Visualization of the Minmum Crossing Number of a Graph. Master’s Thesis, University of Nevada, Reno, NV 89557, August 1998. [TH97] U. Tadjiev and F. Harris, Jr., Parallel Computation of the Minimum Crossing Number of a Graph. Proc. 8th SIAM Conf. on Parallel Process. for Sci. Comput. Minneapolis, Minnesota, March 14-17, 1997. [TH96] J. Thorpe and F. Harris, Jr. A parallel stochastic optimization algorithm for finding the mappings of the rectilinear minimal crossing problem. Ars Comb., 43:135-148, 1996. [Y63] J. Youngs, Minimal imbeddings and the genus of a graph, J. Math. Mech., 12 (1963), pp. 303-315. [YFMH04] B. Yuan, J. R. Fredrickson, S. C. Martin, F. Harris, Jr. A generic queuing system for computationally intensive problems. Submitted for publication, May 2004.