# An Evolutionary Formulation of the Crossing Number Problem

Authors: Che Sheng Gan; Wee Chiat Alan Tan; Voon Chet Koo; Kwang Hwai Mak
Journal: Discrete Dynamics in Nature and Society
 (2009)

---

## Abstract

A graph drawing algorithm is presented which results in complete graphs having minimum crossings equal to that of Guy's conjecture. It is then generalized and formulated in an evolutionary algorithm (EA) to perform constrained search for the crossing numbers. The main objective of this work is to present a suitable two-dimensional scheme which can greatly reduce the complexity of finding crossing numbers by using computer. Program performance criteria are presented and discussed. It is shown that the EA implementation provides good confirmation of the predicted crossing numbers.


---

## Body

## 1. Introduction

LetG be a graph. The crossing number of G, denoted by cr(G), is the minimum number of pairwise intersections of its edges when G is drawn in the plane. Undefined terms in this paper can be found in [1].Problem about the crossing number of a graph is an area of active research in both applied and algorithmic graph theory. Beside being a challenging problem in itself, it also finds applications in areas of network design and circuit layout. The crossing numbers problem was proposed in early 1970s [2, 3]. It has been shown that the problem of determining the crossing number of a given graph is NP-complete [4].There are some known results or conjectures for some families of graphs including complete graphs, bipartite graphs, and product of cycles. In particular, the following is known as Guy’s conjecture [5]:(1.1)cr(Kp)=⌊p/2⌋·⌊(p-1)/2⌋·⌊(p-2)/2⌋·⌊(p-3)/2⌋4,
where Kp is the complete graph of order p. Some values of (1.1) for p= 5, 6,…, 12 are 1, 3, 9, 18, 36, 60, 100, and 150. Guy’s conjecture holds true for complete graphs of up to p=12 and provides a known upper bound for p>12 [6]. Various optimization algorithms [7–9] have been used in the search for the crossing numbers although none has successfully violated the conjecture. In this paper, a graph drawing algorithm is presented which results in complete graphs having the same crossing number given by Guy’s conjecture. A natural extension of this algorithm is then used as the underlying scheme in an evolutionary algorithm (EA) that performs a constrained search for the crossing numbers of complete graphs.


## 2. Graph Drawing Algorithm

In this section, a graph drawing algorithm is proposed, which achieves Guy’s conjecture. An article by Archdeacon [10] provided a helpful starting point for the graph drawing algorithm. The key strategy of this drawing method lies in the connection of vertices by weighing possible edge directions by their positive winding number. In other words, the direction of an edge connecting a top vertex to a bottom one is chosen according to the minimum-length criterion. It is plausible that such a method could produce a drawing with the minimum number of crossings since an edge of minimum length would seem to have lessened its chance of intersecting with other edges. A complete graph of order 5 drawn using this method is shown in Figure 1. Note also that there are two groups of vertices on the top and bottom surfaces of the cylinder connected amongst each other.Figure 1
K5 drawn on a cylinder using the minimum-length rule.The three-dimensional visualization required by such a method is quite difficult for largep. We simplify the drawing by making a vertical cut on the curved surface of the cylinder along its entire length and “unfolding” it into a rectangular plane as in Figure 2. The resulting vertical boundaries are now represented by vertical dotted lines.Figure 2
Mapping ofK5 from cylinder to plane.In such drawings, edges corresponding to those on the top and bottom surfaces of the cylinder are not shown and their crossings will be referred to asexternal crossings as opposed to those on the curved surface of the cylinder which will be referred to as internal crossings. The reason for the absence of external crossings is due to the fact that their number can easily be determined by Cr4 where r is the number of top or bottom vertices.It should be noted that this drawing method serves no purpose other than to verify the upper bound according to Guy’s conjecture (forp≤12 it also verifies the actual crossing number). It is deterministic and hence it does not actually search for a drawing that satisfies the minimum number of crossings. Of course, if the conjecture is proven to be true, then the upper bound is equal to the minimum crossing numbers. The corresponding algorithm is presented as follows.Algorithm 2 A (drawing the complete graph with minimum crossing).
A1.
Partitions the vertices ofKp into U (the set of upper vertices) and V (the set of lower vertices):
A1.1.
U = {ui}   for 0 ≤i≤m-1, where m=⌈p/2⌉,A1.2.
V = {vj}  for 0 ≤j≤n-1, where n=p-m.A2.
Place the vertices ofU andV on two parallel lines (called the upper and the lower lines) that are separated by unity distance:
A2.1.
placeu0(v0) at x=0 and x=m×n on the upper (lower) line,A2.2.
place the remainingui(vj) between x=0 and x=m×n at intervals of length n(m) on the upper (lower) line,A2.3.
u0 at x=0(x=m×n) is joined to v0 at x=0(x=m×n),A2.4.
ui is joined to each vj either by a continuous line or a broken line which crosses the line x=0 or x=m×n subject to the minimum length or the positive direction criteria (the direction is positive for the right going lines).Figure3 shows the application of this drawing algorithm on K6 and K9. The total number of crossings is calculated as the sum of the internal crossings and the upper and lower external crossings.Figure 3
K6 and K9 drawn using Algorithm A.


## 3. The Evolutionary Algorithm (EA)

### 3.1. Introduction

In this section, we present an evolutionary formulation for the crossing number problem. The proposed algorithm initializes by randomly generating a population of genomes. As shown in Figure4, initial populations of size N are selected from the solution space of 2p, where each genome encodes a complete graph of order p by a binary-valued ⌈p/2⌉×⌊p/2⌋ adjacency matrix. Figure 5 illustrates an example of the coding convention for K5.Figure 4
An initial populationG0 containing N genomes is selected from the solution space of 2p.Figure 5
The coding convention for genomeg3∈K5; coding conventions, R: right-going edge, L: left-going edge, for the case where  (ui,vi) forms a vertical line, either R or L can be used.From the initial population, the evolutionary algorithm (Algorithm B) recombines, mutates, and selects genomes for the population of subsequent generations. The algorithm terminates afterK generations, or when the optimum solution (the conjecture upper bound) is achieved.Algorithm 3.1 B (optimization search for minimum crossing based on EA).
B1
Initialization.
An initial population,G0, of N genomes is randomly drawn,SetG0←{g1,g2,…,gN}.B2
Fork=1 to K, make the following:
B2.1
Recombination.
two parent genomesga and gb are selected from the population Gk-1 using Roulette selection and recombined to produce an offspring genome gr. This process is repeated Nr times:InitializeGkr← 0.Forn=1 to Nr, do:
Pickga← roulette (Gk-1) and gb← roulette (Gk-1-ga).Makegr← recombine (ga,gb).UpdateGkr←Gkr+gr.End ForUpdateGkr←Gk-1+Gkr.B2.2
Mutation.
Every genome in the populationGkr is mutated at a (preset) mutation rate Pmut:InitializeGkm←0.For everygn∈Gkr, do:
Makegm← mutate (Pmut,gn).UpdateGkm←Gkm+gm.End ForB2.3
Selection.
The selection stage is divided into two parts, that is,Elite selection and Non-elite selection. In the elite selection, the best Ns genomes of the population Gkm is initially selected and removed from Gkm. The remaining N-Ns genomes are then selected from the depleted Gkm to retain the population size at N:InitializeGk←0.End ForEnd For
End For


### 3.2. Evolutionary Functions

To evaluate the “goodness” of a genome in a population, afitness function is required. A genome with a high fitness value is more likely to survive than one with a low fitness value. For this particular problem, the following fitness function F is used to evaluate the fitness of graph g:(3.1)F(g)=max(0,1-log2(cr(g)cr0)),
where cr(g)  is the crossing number of graph g and cr0 is the conjectured lower bound of cr(g). As shown in Figure 6, the fitness function is a monotone function which has the widest dynamic range as compared to other functions. If Guy’s conjecture holds true, the optimum (maximum) value for F(g) is 1. A value greater than 1 will indicate a violation of the conjecture.Figure 6
Fitness Functions.Roulette selection is a selection mechanism in which a genome of population G is picked based on some fitness measure. To select a genome from the population G={g1,g2,…,gN}, a random number r is drawn from the uniform distribution [0,1]. Genome gn is selected if(3.2)∑i=1n-1F(gi)F0≤r<∑i=1nF(gi)F0,
where(3.3)F0=∑i=1NF(gi).The function recombine (ga,gb) combines two parent genomes gaand gb to produce an offspring genome. The offspring gr inherits genetic material from ga with a probabilityF(ga)/F(ga)+F(gb), otherwise, genetic material from gb is inherited. The recombination process is illustrated in Figure 7.Figure 7
The recombination process.The function mutate (Pmut,g) mutates genome g with mutation rate Pmut. Mutation generally involves toggling the binary value of the coded genome. The function bestof (G) picks the best genome gb from population G, where
(3.4)b=argmax{F(gn):∀gn∈G}.


## 3.1. Introduction

In this section, we present an evolutionary formulation for the crossing number problem. The proposed algorithm initializes by randomly generating a population of genomes. As shown in Figure4, initial populations of size N are selected from the solution space of 2p, where each genome encodes a complete graph of order p by a binary-valued ⌈p/2⌉×⌊p/2⌋ adjacency matrix. Figure 5 illustrates an example of the coding convention for K5.Figure 4
An initial populationG0 containing N genomes is selected from the solution space of 2p.Figure 5
The coding convention for genomeg3∈K5; coding conventions, R: right-going edge, L: left-going edge, for the case where  (ui,vi) forms a vertical line, either R or L can be used.From the initial population, the evolutionary algorithm (Algorithm B) recombines, mutates, and selects genomes for the population of subsequent generations. The algorithm terminates afterK generations, or when the optimum solution (the conjecture upper bound) is achieved.Algorithm 3.1 B (optimization search for minimum crossing based on EA).
B1
Initialization.
An initial population,G0, of N genomes is randomly drawn,SetG0←{g1,g2,…,gN}.B2
Fork=1 to K, make the following:
B2.1
Recombination.
two parent genomesga and gb are selected from the population Gk-1 using Roulette selection and recombined to produce an offspring genome gr. This process is repeated Nr times:InitializeGkr← 0.Forn=1 to Nr, do:
Pickga← roulette (Gk-1) and gb← roulette (Gk-1-ga).Makegr← recombine (ga,gb).UpdateGkr←Gkr+gr.End ForUpdateGkr←Gk-1+Gkr.B2.2
Mutation.
Every genome in the populationGkr is mutated at a (preset) mutation rate Pmut:InitializeGkm←0.For everygn∈Gkr, do:
Makegm← mutate (Pmut,gn).UpdateGkm←Gkm+gm.End ForB2.3
Selection.
The selection stage is divided into two parts, that is,Elite selection and Non-elite selection. In the elite selection, the best Ns genomes of the population Gkm is initially selected and removed from Gkm. The remaining N-Ns genomes are then selected from the depleted Gkm to retain the population size at N:InitializeGk←0.End ForEnd For
End For


## 3.2. Evolutionary Functions

To evaluate the “goodness” of a genome in a population, afitness function is required. A genome with a high fitness value is more likely to survive than one with a low fitness value. For this particular problem, the following fitness function F is used to evaluate the fitness of graph g:(3.1)F(g)=max(0,1-log2(cr(g)cr0)),
where cr(g)  is the crossing number of graph g and cr0 is the conjectured lower bound of cr(g). As shown in Figure 6, the fitness function is a monotone function which has the widest dynamic range as compared to other functions. If Guy’s conjecture holds true, the optimum (maximum) value for F(g) is 1. A value greater than 1 will indicate a violation of the conjecture.Figure 6
Fitness Functions.Roulette selection is a selection mechanism in which a genome of population G is picked based on some fitness measure. To select a genome from the population G={g1,g2,…,gN}, a random number r is drawn from the uniform distribution [0,1]. Genome gn is selected if(3.2)∑i=1n-1F(gi)F0≤r<∑i=1nF(gi)F0,
where(3.3)F0=∑i=1NF(gi).The function recombine (ga,gb) combines two parent genomes gaand gb to produce an offspring genome. The offspring gr inherits genetic material from ga with a probabilityF(ga)/F(ga)+F(gb), otherwise, genetic material from gb is inherited. The recombination process is illustrated in Figure 7.Figure 7
The recombination process.The function mutate (Pmut,g) mutates genome g with mutation rate Pmut. Mutation generally involves toggling the binary value of the coded genome. The function bestof (G) picks the best genome gb from population G, where
(3.4)b=argmax{F(gn):∀gn∈G}.


## 4. Performance Evaluation

The EA algorithm is deemed successful when it finds the number of crossings equal to (1.1). We will examine the performance of the algorithm based on the number of functions evaluated to achieve the conjectured upper bound. Four variables are considered for such evaluation: graph order (p), mating probability (Pmate) defined as Nr/N, mutation rate (Pmut), and elite percentage (Pelite) defined as Ns/N. In each experiment, three of the four input variables are held constant while the variable selected for evaluation takes on values of a given range. Figures 8, 9, and 10 summarizes the experiment results by varying the Pmate, Pmut, and Pelite, at p=12. Each experiment is conducted for 50 trials and the final result is averaged over these 50 trials. In a subsequent experiment shown in Figure 11, a set of optimum parameters (Pmate=0.5,Pmut=0.05, and Pelite=0.1) is applied to search for the conjecture upper bound. Finally, Table 1 summarizes the success rates of the proposed formulation for graph order up to 20. The success rates improve as the population size (N) and the number of iterations increase. However, this will increase the computational time since larger solution space is evaluated. Based on the empirical data, N=50 and Iteration = 200 are good compromise for this problem.Table 1
Success Rates of the EA.
Graph order,pN=25,N=25,N=50,N=50,Max iteration = 100Max iteration = 200Max iteration = 100Max iteration = 200Average iterationSuccess rate (%)Average iterationSuccess rate (%)Average iterationSuccess rate (%)Average iterationSuccess rate (%)5110011001100110061100110011001100711001100110011008310041002100210094100510031003100109100910061007100111110011100810081001221100201001510015100132510024100181001710014429842100301002810015471004810033100351001672847310050985910017756698100589468100188916137827746108961982214764793115942010001541889215664Figure 8
Plot of number of functions evaluated against mating probability (p=12, Pmut=0.05, Pelite=0.1).Figure 9
Plot of number of functions evaluated against mutation rate (p=12,Pmate=0.5,Pelite=0.1).Figure 10
Plot of number of functions evaluated against elite percentage (p=12,Pmate=0.5,Pmut=0.05).Figure 11
Plot of number of functions evaluated against graph order (Pmate=0.5,Pmut=0.05,Pelite=0.1).


## 5. Conclusions and Future Work

In this paper a graph-drawing algorithm is proposed to represent the graphical equivalent of Guy’s conjecture. The results are then extended, generalized, and employed in an evolutionary algorithm that performed a constrained search for the crossing number.Performance of the EA is evaluated and presented. It is demonstrated that the EA is successful in finding the upper bound as set by (1.1). The success of the EA is dependent on the actual evolutionary mechanisms of selection, recombination, mutation, and reinsertion. As expected, the number of generations required to achieve optimum solution increases as the graph order becomes larger. The algorithm performed well at lower rates of mutation, which prevents the EA from degenerating into a random search.It is natural to ask whether a graph with fewer crossings can be found by removing adherence to the conjecture upper bound. The future work is focused on optimizing various parameters and generalizing the algorithm such that given an initial set of randomly drawn complete graphs, an optimized solution is to be found with minimum crossing numbers.



---

*Source: 154015-2009-09-23.xml*