Algorithms for the fixed linear crossing number problem.
several heuristics and an exact branch-and-bound algorithm are described for the fixed linear crossing number problem (FLCNP). An experimental study comparing the heuristics on a large set of test graphs is given. FLCNP is similar to the 2-page book crossing number problem in which the vertices of a graph are optimally placed on a horizontal "node line" in the plane, each edge is drawn as an arc in one half-plane (page), and the objective is to minimize the number of edge crossings. In this restricted version of the problem, the order of the vertices along the node line is predetermined and fixed. FLCNP belongs to the class of NP-hard optimization problems (IEEE Trans. Comput. 39 (1) (1990) 124). The heuristics are tested and compared on a variety of graphs including some "real world" instances of interconnection networks proposed as models for parallel computing. The experimental results indicate that a heuristic based on the neural network model yields near-optimal solutions and outperforms the other heuristics. Also, experiments show the exact algorithm to be feasible for graphs with up to 50 edges, in general, although the quality of the initial upper bound is more critical to runing time than graph size.
Introduction
Recently, several linear graph layout problems have been the subject of study.
Given a set of vertices, the problem involves placing the vertices along a horizontal
\node line" in the plane and then adding edges as specied by the
interconnection pattern. The node line, or \spine", divides the plane into two
half-planes, also called \pages", corresponding to the two pages of an open
book. Some examples of linear layout problems are the bandwith problem [8],
the book thickness problem [2,29], the pagenumber problem [9,32], the boundary
VLSI layout problem [50], and the single-row routing problem [37]. For
Preprint submitted to Elsevier Science 22 August 2001
(a) (b)

Figure

1. Fixed linear embedding of the complete graph K 6
crossings; (b)  L (K 6
surveys of linear layout problems, see [4,51]. Linear layout is important in several
applications, e.g., sorting with parallel stacks [49], fault-tolerant processor
array design [39], and VLSI design [9].
In this paper we study a restricted version of linear graph layout in which the
vertex order is predetermined and xed along the node line and each edge is
drawn as an arc in one of the two pages. The objective is to embed the edges
so that the total number of crossings is minimized (see Figure 1). We refer
to this as the xed linear crossing number problem (FLCNP) and denote the
minimum number of crossings by  L (G) for a graph G.
FLCNP was shown to be NP-hard in [33]. Single-row routing with the restriction
that wires do not cross the node line is similar to FLCNP, although its
objective is to nd a layout (if any) with no crossings. FLCNP also appears as
a subproblem in communications network management graphics facilities such
as CNMgraf [21]. The problem is also of general interest in graph drawing and
graphical visualization systems where crossing minimization is an aesthetic
criterion used to measure the quality of a graph drawing [14,48].
A variant of the problem in which the vertex positions are not xed is studied
in [35] and a heuristic is given for its solution. A related parameter is the
book crossing number of a graph G,  k (G), which is the minimum number of
crossings in a k-page embedding of G [2,29,42]. Note that vertex positions
are not xed and hence it is rst necessary to nd an optimal ordering of
vertices in order to determine  k (G). The book crossing number problem is
closely related to the pagenumber problem. The pagenumber of a graph is the
minimum number of pages necessary to embed the edges of a graph (each
edge on one page) without crossings. It is known that outerplanar graphs
comprise the 1-page embeddable graphs [2], that subhamiltonian graphs, i.e.,
subgraphs of planar hamiltonian graphs, are precisely the 2-page embeddable
graphs [2], and that planar graphs are 4-page embeddable [52]. Nonplanar
graphs, however, require at least three pages [2]. A recent survey of the k-
pagenumber and general crossing number problem on various surfaces can be
found in [40]. Crossing minimization has also been studied for the case of two
l

Figure

2. Edge crossing condition i < j < k < l.
levels of vertices in [17] and [28], and for the general case in [15].
Let (G) denote the general planar crossing number of a graph G. In [43] it is
shown that  2 (G)  (G). Observe that  L (G)   2 (G), since the achievement
of minimum crossings is dependent on an optimal ordering of vertices on the
node line.
ng. A 2-page drawing of a graph is represented
by a pair of binary adjacency matrices A[ ] and B[ ]. For each edge ij, A[i; j]
(B[i; j]) is embedded in the upper (lower) page and 0, otherwise.
Then any pair of edges ik and jl cross in a drawing
and both lie in the same page (see Figure 2). Hence, the following formula
counts the number of crossings in a 2-page drawing D:
In this paper, we present eight dierent heuristics for FLCNP as well as a
branch-and-bound algorithm for nding exact solutions. We test the methods
on random graphs in addition to \real world" instances of graphs which model
some interconnection topologies proposed as architectures for parallel comput-
ing. Our results show that a heuristic based on the neural network model of
computation, which we simulate with a sequential algorithm, is a highly effective
method for computing  L (G). The heuristic consistently outperforms
the other heuristics both in solution quality and running time. Furthermore,
for graphs with up to approximately 50 edges, the exact algorithm is a practical
choice, although its performance is highly dependent on the quality of
the initial upper bound value. Hence, the algorithms we present serve as useful
methods for computing  L (G) and also for obtaining good linear 2-page
layouts of various networks. Also, since  L (G)  (G), they provide upper
bounds for the general planar crossing number of a graph G.
We begin by presenting some theoretical bounds, followed by a description of
the algorithms, and conclude with an experimental analysis.
Theoretical Bounds
We present some theoretical upper and lower bounds for  L (G) which are used
in assessing the performance of the algorithms. Throughout our discussion we
assume good drawings of graphs, in which the following conditions hold:
(i) an edge does not cross itself,
(ii) edges with common endpoints do not cross,
(iii) any intersection of two edges is a crossing rather than tangential,
(iv) no three edges have a common crossing, and
(v) any pair of edges cross at most once.
It is a routine exercise to show, for any graph G, there is a good drawing of
G having the minimum number of crossings.
In [29],  1 (G) was dened as the
outerplanar crossing number but no results were given. However, in [42] the
following results are shown:
Theorem 1.  1 2.
Theorem 2.  1
for n  4; m  3n.
Theorem 3.  k (G)  m 3
27knAlso, the following result can be deduced:
Theorem 4.  1 (K n
Proof. This is equivalent to the problem of arranging the vertices of the
graph on the boundary of a circle and drawing the edges as chords. Then for
each 4-tuple of vertices (i; j; k; l) along the boundary, with labels satisfying
there is precisely one crossing caused by edges ik and jl.
Hence,B @ n1
C A gives the correct number of crossings. 2
The following result for K n was previously shown in [24] (see also [22,23]):
Theorem 5.  2 (K n
Actually, equality has been shown for in the above formula.
In [13], an alternate upper bound based on the adjacency matrix is given for
when drawn on k pages, and tables of results for dierent n and k
values are given. The results for with those of Theorem 5.
Theorem 6.
Proof. We construct a 2-page drawing of G with dm=2e edges in one page and
bm=2c in the other. Now, assuming in the worst case that each edge crosses
every other edge exactly once, we have at mostB @ dm=2e1
C A cross-
ings. Expanding this sum and using the identity dn=2e
at the given inequality. 2
Also, in [42] the following result and a greedy algorithm are given for constructing
a k-page drawing of G from a 1-page drawing with the indicated
number of crossings:
Theorem 7.  k (G)   1 (G)=k.
3 The Heuristics
We developed and tested eight dierent heuristics. They are grouped into two
general categories | greedy and non-greedy. The two greedy heuristics dier
only in the order in which edges are added to the layout. Descriptions of the
heuristics are given in the following sections.
We assume that vertices are xed in the order 1; 2; :::; n along the node line.
As a pre-processing step to each algorithm, we remove all insignicant edges.
Observe that edges between consecutive vertices on the node line and the edge
1n cannot be involved in crossings according to the constraints of the problem.
Also, if there is a vertex k such that no edge ij, i < k < j, exists, then edges 1k
and kn cannot cause crossings. Hence, these edges are insignicant and may
be ignored without aecting the nal solution. At the same time, the problem
size is reduced so that larger instances can be solved. The output of each
heuristic is the minimum number of crossings obtained and the corresponding
embedding.
3.1 Greedy Heuristics
The Greedy heuristic adds edges to the layout in row-major order of the adjacency
matrix of the graph, that is, rst all edges 1i are added in increasing
order of i-value, then all edges 2i in increasing i-value order, etc. At each step,
an edge is embedded in the page (upper or lower) which results in the smallest
increase in the number of crossings. Ties are broken by placing the edge in
the upper page. Heuristic Gr-ran uses the same approach but adds edges in
random order.
3.2 Maximal Planar Heuristic
Heuristic Mplan nds a maximal planar subgraph in each page. In the rst
phase, edges are added in row-major order of the adjacency matrix to the
upper page. If an edge causes a crossing, it is put aside until the second phase.
In the second phase, all edges put aside in the rst phase are added to the
lower page. If an edge causes a crossing, it is once again put aside. In the third
phase, any edges put aside in the second phase are added to the page with the
smallest increase in crossings.
3.3 Edge-Length Heuristic
Heuristic E-len initially orders all edges non-increasingly by their \length",
i.e., ju vj for edge uv. The intuition here is that longer edges have a greater
potential for crossings than shorter edges and hence should be embedded rst.
Each edge is added one at a time to the page of smallest increase in crossings.
3.4 One-Page Heuristic
This is essentially the same method described in [42] and implied by Theorem
7 with 2. Heuristic 1-page initially embeds all edges in the upper page.

Figure

3. Fixed embeddings for base cases of dynamic programming heuristic.
This is followed by a \local improvement" phase in which each edge is moved
to the lower page if it results in fewer crossings. Edges are considered for
movement in order of non-increasing local crossing number, i.e., the number
of crossings involving an edge.
3.5 Dynamic Programming Heuristic
Unfortunately, FLCNP does not satisfy the principle of optimality which says
that in an optimal sequence of decisions each subsequence must also be opti-
mal. Subgraphs embedded optimally earlier in the process do not necessarily
lead to optimal embeddings of larger subgraphs when edges are added between
the smaller subgraphs later on. However, this does not preclude the potential
benet of a dynamic programming approach to the problem as a heuristic so-
lution. If most crossings are localized within relatively small subgraphs along
the node line for a given graph, a dynamic programming method may produce
a good solution.
Let G i::j denote the subgraph induced by consecutive vertices i::j along the
node line, and let cr[i; k; j] be the number of crossings in the subgraph
G i::k
is the set of \link edges" between G i::k and
G k+1::j . We compute cr[i; k; j] greedily by adding each link edge to the page
with the smallest increase in crossings. This leads to a recurrence for the number
of crossings, nc[1; n], computed by a dynamic programming solution:
The base cases for the algorithm are the subgraphs of order 2 4. Optimal
embeddings for these are predetermined and shown in Figure 3.
3.6 Bisection Heuristic
This heuristic uses a straightforward divide-and-conquer approach. The original
graph G 1::n is initially bisected into two smaller subgraphs G 1::b nc and
G b nc+1::n by temporarily removing the link edges between them. Each sub-graph
is then bisected recursively in the same manner until subgraphs of order
4 or less are obtained. Embeddings for these base cases are the same as those
shown in Figure 3. When combining smaller subgraphs, link edges between
the subgraphs are embedded in greedy fashion as before. A similar method
is described in [3], although the way in which edges are re-inserted into the
embedding after the bisection phase is not clearly specied.
3.7 Neural Network Heuristic
This heuristic is based on the neural network model of parallel computation
[27]. In this model there are a large number of simple processing elements
called We assume the McCulloch-Pitts binary neuron in which each
element has a binary state [34]. This model has also been used for the graph
planarization problem [47]. For testing purposes, a sequential simulator of
the actual parallel algorithm was used. The model uses 2m neurons for a
graph with m edges. With each edge is associated an \up" and a \down"
neuron, representing the two pages of the plane. Brie
y, two kinds of forces,
'excitatory' and `inhibitory', are present in the neural network. The presence
of an edge uv in a graph encourages the two neurons for the edge to re as the
excitatory force, while neurons of crossing edges are discouraged from ring
as the inhibitory force. At each iteration of the main processing loop, neuron
values are recalculated according to specied motion equations. Eventually,
after several iterations, either an 'up' or `down' neuron for each edge is in an
excitatory state and a nal embedding is obtained.
It is straightforward to simulate the parallel algorithm with a sequential algo-
rithm. Whereas, in the parallel algorithm, the output values of the neurons are
simultaneously updated outside of the motion equation loop, in the sequential
simulator, the output value of each neuron is individually computed in
sequence as soon as the input of the neuron is evaluated inside of the motion
equation loop. A drawback to neural network algorithms is the possibility of
non-convergence. Typically, a constant limit is imposed upon the number of
iterations of the motion equation computation loop, and the process is terminated
if convergence to the equilibrium state has not occurred by the limit.
Full details of the heuristic are given in [11].

Table
Time Complexities of the Heuristics.
Heuristic Time Complexity
Greedy O(m 2 )
Gr-ran O(m 2 )
Mplan O(m 2 )
1-page O(m 2 )
dynamic O(m 2
bisection O(n 4 )
neural O(m)
4 Time Complexities of the Heuristics
The time complexities of the heuristics and exact algorithm are given in Table
1. For the greedy, maximal planar, edge-length, and one-page heuristics, the
total time is dominated by the time to calculate the number of crossings
after each edge is added to the layout, which is O(n 4 ) if eq. (1) is directly
applied. Instead, however, we use a \dynamic" crossing recalculation method
which only checks for crossings involving the edge just added. This lowers the
recalculation time to O(m) for each edge added. For the dynamic programming
heuristic, there are a total of O(n 2 ) subgraphs to process, and each subgraph
requires O(m 2 ) time to add link edges and recalculate crossings. The time for
the bisection heuristic is given by the recurrence T
where O(n 4 ) is the time to merge each pair of subgraphs, and this recurrence
has the solution O(n 4 ).
The sequential simulator of the neural network heuristic has a main loop with
a number of iterations dependent on the rate of convergence of the system to a
stable state, which is not bounded by any function of the input size. However,
in experimental testing, the maximum number of loop iterations observed for
any test graph was 84. There are O(1) operations performed on each of the m
edge neurons per iteration. Hence, the time complexity is O(m).
5 An Exact Algorithm
The number of xed linear layouts of a graph is 2 m . Ignoring up to n insignificant
edges, this yields at most 2 n(n 3)=2 dierent layouts. Since any layout
has a \mirror image" (symmetric) drawing with the same number of crossings
obtained by switching the embeddings between the two pages, only one
half of this number need be checked, or 2 n(n 3)=2 1 . A branch-and-bound algorithm
was developed to nd optimal solutions by enumerating all possible
embeddings of edges subject to optimization bound conditions. Two bounding
conditions were applied to prune partial solution paths in the search tree. A
path (branch) of the tree is pruned if:
(1) the number of crossings in the partial solution exceeds the current global
upper bound, or
(2) the number of crossings in the partial solution plus the number of extra
crossings resulting from adding each remaining edge to the partial embeddding
greedily and independently of other remaining edges exceeds the current global
upper bound.
A backtracking algorithm was developed to enumerate the embeddings and
apply the bounding conditions. An initial global upper bound was obtained
from the best solution generated by the theoretical bounds and the heuristics.
As with the heuristics, the output of the algorithm is the number of crossings
obtained and the corresponding embedding.
6 Test Graphs
Several classes of test graphs were generated, and they are brie
y described
in the following sections. Since we were interested in obtaining good upper
bounds for the planar crossing number of families of graphs, we generated
several types of hamiltonian graphs. Many networks proposed as models of
parallel computer architectures are hamiltonian. For each graph G, the strategy
was to x the vertices along the node line in the order of a hamiltonian
cycle, if possible, since G may have a crossing-minimal drawing in which there
is a hamiltonian cycle which is not crossed by an edge. If the vertices are
then positioned along the node line in the given hamiltonian order, and the
edges are optimally drawn, then such a drawing would have (G) crossings.
However, as is discussed in [9], not all hamiltonian cycle orderings of vertices
correspond to an optimal vertex ordering, that is, one that leads to a linear
layout with a number of crossings equivalent to the planar crossing number
of the graph. To nd an optimal cycle, for example, for the d-dimensional hypercube
, as many as 2 d 3 d! cycles [41], in the worst case, would have to be
generated and tested, and this would be impractical for large d. Nevertheless,
by using a hamiltonian ordering of vertices on the node line, the likelihood of
computing the planar crossing number of the graph was increased.
6.1 Random Graphs
We used the traditional model G n;p of random graphs [6] formed by independently
including each edge of K n with probability
random graphs of order was made to nd a
hamiltonian cycle in any graph, due to the computational di-culty of this
problem. Hence, the vertices were simply positioned along the node line in the
order
6.2 Interconnection Network Graphs
Many interconnection topologies have been proposed for parallel computing
architectures. While optimal book embeddings have been investigated for several
of the networks (e.g., [9,26]), the xed linear crossing number has not to
our knowledge been investigated. Detailed descriptions of many of these networks
can be found in [30,53]. Here we provide only brief descriptions. All of
the network graphs generated are hamiltonian. Since hamiltonian cycles may
be easily found in these graphs, vertices were positioned along the node line in
hamiltonian order for the testing, with the hope of obtaining better approximations
to the planar crossing number of the graph, as discussed earlier.
6.2.1 Hypercubic Networks
The hypercube, Q d , of dimension d, is a d-regular graph with 2 d vertices and
Each vertex is labelled by a distinct d-bit binary string, and
two vertices are adjacent if they dier in exactly one bit. Q 3 is shown in Figure
4(a). Hypercubes of dimension
Several derivatives of the hypercube have also been proposed. These are generally
referred to as hypercubic networks. While the hypercube has unbounded
vertex degree, according to its dimension, most of the hypercubic networks
have constant degree bounds, usually 3 or 4, making them less dense with
increasing order.
The cube-connected-cycles [36], CCC d , of dimension d is formed from Q d by
replacing each vertex u with a d-cycle of vertices in CCC d and then joining
each cycle vertex to a cycle vertex of the corresponding neighbor of u in

Figure

4(b) shows CCC 3 . CCC d has d2 d vertices, 3d2 d 1 edges, and is
3-regular. The instances
The twisted cube [7], TQ d , has the same order, size, and regularity as Q d . TQ d
is formed by twisting one pair of edges in a shortest cycle (4-cycle) of Q d .

Figure

4(c) displays TQ 3 . TQ d of dimension
The crossed cube, CQ d , is dened in [18]. Like Q d , CQ d has 2 d vertices, d2 d 1
edges, and is d-regular. Figure 4(d) displays CQ 3 . CQ d of dimension
were generated.
The folded cube [19], FLQ d , is formed from Q d by adding the 2 d 1 extra
complementary edges fu;
ug for each vertex u where u is a d-bit binary string.

Figure

4(e) displays FLQ 3 . FLQ d of dimension
The hamming cube [16], HQ d , of dimension d, has 2 d vertices and (d+2)2 d 1 2
edges. HQ d has minimum degree d + 1, maximum degree 2d 1, and is a
supergraph of Q d . Figure 4(f) displays HQ 3 . HQ d of dimension
generated.
The binary de Bruijn graph [12], DB d , is a directed graph of 2 d vertices and
arcs. The vertices are labelled by the 2 d binary d-tuples. There is an arc
from vertex x 1 :::x d to vertex y 1 :::y d i x 2 :::x As a result, vertices
00:::0 and 11:::1 have self-loops. Undirected de Bruijn graphs [1], UDB d , are
formed from directed de Bruijn graphs by ignoring the orientations of the
edges and deleting the two self-loops, which are irrelevant in determining the
crossing number. UDB d has 2 d vertices, 2 d+1 2 edges, and maximum degree
4.

Figure

4(g) displays UDB 3 which is planar. UBD d of dimension
were generated.
The wrapped butter
y graph [30], WBF d , of dimension d has d2 d vertices and
d2 d+1 edges. The graph is 4-regular. Figure 5(f) displays WBF 3 . WBF d of
dimension
The shue-exchange graph [30] SX d , has 2 d vertices and 3  2 d 1 edges. uv
is an edge of SX d if either u and v, which are d-bit binary strings, dier in
precisely the last bit, or u is a left or right cyclic shift of v. For embedding
purposes, we ignore the two self-loop edges at vertices 00:::0 and 11:::1, which
results in a graph with 3  2 d 1 2 edges. Pendant vertices 00:::01 and 11:::10
may also be ignored to facilitate a hamiltonian vertex ordering along the node
line.

Figure

5(d) displays SX 3 . SX d of dimension
(a) (b) (c)
(d) (e)

Figure

4. Some interconnection networks: (a) hypercube
conected cycles CCC 3 ; (c) twisted cube TQ 3 ; (d) crossed cube CQ 3 ; (e) folded
cube hamming cube HQ 3 ; (g) undirected de Bruijn graph UDB 3 .
6.2.2 Other Networks
The d  d torus, T d;d , is the graphical cross product of the cycles C d and C d .

Figure

5(a) displays T 4;4 . Torii T d;d , for
The star graph [45], ST d , has d! vertices labelled by all permutations of f1; 2; 3; :::; dg.
Two vertices are adjacent i the corresponding permutations dier only in the
rst and one other position. Hence, ST d has (d 1)d!=2 edges and is (d 1)-
regular. Figure 5(b) displays ST 4 . ST d for
The pancake graph [45], PK d , has d! vertices labelled by all permutations of
the elements dg. Two vertices are adjacent i one can be obtained
by
ipping the rst i elements of the other for some i  2. PK d has the same
order and size as ST d and is also (d 1)-regular. Figure 5(c) displays PK 4 .
PK d for
The pyramid graph [30], PM d , has d levels of vertices, with each level k, 0
k < d, having 4 d vertices, for a total of (4 d 1)=3 vertices. The interconnection
structure of PM 3 is shown in Figure 5(e). PM d for
(a) (c)
(d)
(b)

Figure

5. Additional interconnection networks: (a) torus T 4;4 ; (b) star graph
wrapped butter
6.3 Other Graph Families
Also included in the testing were complete graphs, K n , for
circulant graphs. The circulant graph [5], C n (a
a k < (n + 1)=2, is a regular hamiltonian graph with n vertices, with vertices
n) adjacent to each vertex i. C n (a
20::46 and various a i values were generated. C 8 (1; 2; 4) is shown in Figure
5(g). Vertices were placed along the node line in hamiltonian order for the
testing.
7 Experimental Results
All algorithms were implemented in the C language on a DEC AlphaServer
2100A 5/300 workstation with 300 MHz cpu speed and 512 megabytes of
RAM.
Test graph size was limited by the excessive time requirements of the bisection
and dynamic heuristics and the branch-and-bound algorithm. The largest
test graph contained 1016 edges. Due to the memory needed by the program
to store all of the subgraphs generated by bisection and dynamic, it was impossible
to test graphs larger than this with the current implementation and
hardware. The two greedy heuristics and heuristics Mplan, 1-page, Neural, and
E-len, on the other hand, can accommodate much larger graphs.
Results for the dierent classes of graphs are shown in Tables 2-5 and Figures
6-10.

Figure

11 shows a plot of heuristic performance on all 196 test graphs.
For complete graphs (Table 2), both Neural and E-len found optimal solutions
in all cases. The Greedy heuristic had the worst performance on these graphs.
For the hypercubic networks, as indicated by Table 3 and Figure 8, bisect and
dynamic performed poorly, while the remaining heuristics had much better
performance. In particular, neural found the optimal solution for 15 of the 39
test cases.
For the random graphs tested (see Figure 7), the edge density was approximately
the same ( 0:5) for all instances, with some minor variation due
to normal inconsistencies in the pseudorandom number generator. Here, we
dene the edge density of a graph to be m=jE(K n )j for an n-vertex, m-edge
graph.
In

Figure

11, we plotted the number of crossings versus the edge density for
all test graphs. It is interesting to observe that the number of crossings found
by all heuristics increases dramatically after 80 vertices, even though the edge
density is constant. It is likely that the xed vertex orderings along the node
line become more of a factor in heuristic performance as the number of vertices
increases. Due to the rather large scale of the gure, the plot is undetectable
for sparse graphs, until the density exceeds about 0:5. Any dierences in performance
between six of the heuristics (excluding bisect and dynamic) are still
hard to observe after that. Hence, to gain a better perspective of relative
performance, we also compared the heuristics according to a ranking scheme,
where the rank of a heuristic A, was dened to be k, 1  k  8, if A obtained
the k th best solution among the eight heuristics for a given instance. Table 6
shows the overall rankings on all test graphs. Heuristic Neural either had or
tied for the best average rank in 15 of the 17 classes, and also had the best
composite average rank (1:35) of the eight heuristics for all test graphs.
At the other extreme, bisect exhibited the poorest overall performance, nish-
ing last or tied for last in average rank on all graph classes. Its performance
can probably be improved by a more clever method for adding link edges between
subgraphs after the bisection process. The same applies to the dynamic
programming heuristic, although its performance was signicantly better than
bisect.
It is also interesting to examine the degree of optimality of the heuristics in
cases where the optimal solution is known. This is summarized in Table 7.
Optimal solutions were obtained for 95 of the 196 test graphs. Neural found
the optimal solution in 75 (79%) of these cases. Its solution deviated from the
optimal by a total of 38 crossings in the remaining 20 cases, for an average
deviation of 1:9 crossings. The maximum deviation of 6 crossings by Neural
occurred on the circulant graph C 24 (1; 3; 5). For the classes of complete graphs,
torii, de Bruijn, and hypercubic graphs (except hypercubes), Neural found the
optimal or conjectured optimal solution for all test cases with known solutions.
The random greedy heuristic nished second in overall performance with an
average deviation of 1:9 crossings from the optimal solution on 95 graphs. The
standard greedy heuristic, on the other hand, was second to last in perfor-
mance. Hence, the advantage of random edge selection is apparent.
In the tables, the column headings are abbreviated as follows:
Opt.: optimal solution from branch-and-bound algorithm
Greedy: greedy heuristic
Gr-ran: random greedy heuristic
Mplan: maximal planar heuristic
E-len: edge length heuristic
1-page: one-page heuristic
Dyn: dynamic programming heuristic
Bisect: bisection heuristic
Neural: neural network heuristic
Within the Opt. column, in cases where an optimal solution was not obtainable
due to problem size, a pair of values LB:UB indicates the best known theoretical
lower and upper bounds. Except where noted, bounds were obtained
from Theorems 3-7.
We note that for the hypercube, Q 5 , the optimal solution obtained by the
exact algorithm contained 60 crossings. However, a drawing is given in [31]
with only 56 crossings. Hence, the particular hamiltonian cycle used here was
Results for Complete Graphs.
Number of Crossings Found by Heuristic
Graph Opt:  Greedy Gr-ran Mplan E-len 1-page Dyn Bisect Neural
K8
optimal value
conjectured optimal value
not an optimal vertex ordering necessary to achieve the minimum. The same
can be noted for the solutions obtained for the torii T 5;5 and T 7;7 (20 and
48, resp.), which are higher than the known optimal values of 15 and 35,
respectively.
For heuristics Neural and Gr-ran, the best solution obtained from 10 trials per
instance is indicated. As a practical limit, Neural was allowed to iterate up to
5000 times per instance before non-convergence was assumed. However, the
maximum number of iterations observed for any test graph was 84. Moreover,
graph size had no observable eect on the number of iterations.
A comparison of running times for the heuristics on a sampling of 48 graphs
is shown in Figure 12. The times for E-len, Mplan, and 1-page are dwarfed by
those of the dynamic programming heuristic and thus are barely discernible
along the x-axis in the plot. Running times for the bisection heuristic were
somewhat longer than these but still much shorter than the dynamic programming
heuristic.

Figure

12 shows the running times of the heuristics for a representative sampling
of the test cases selected from each of the dierent classes of graphs.
The sharp spikes in the plots for the dynamic and bisection heuristics may
be attributed to instances with a large number of vertices, since this has a
dramatic eect on the depth of recursion and resulting cpu overhead for both
heuristics. The cpu times for the remaining heuristics were all comparatively
fast. In particular, the neural network heuristic required at most 84 iterations
on any instance and ran noticeably faster than the other heuristics in most
cases.
The cpu times for the exact algorithm are shown in Table 8 on a sampling of 17
graphs. The table includes the percentage of the total search space explored. In
Results for Hypercubic Networks.
Number of Crossings Found by Heuristic
Graph n m Opt:  Greedy Gr-ran Mplan E-len 1-page Dyn Bisect Neural
28 34 28 29 29 29 29 34 28
single value indicates optimal solution; pair of values indicates theoretical lower and upper bounds
1 lower bound d(d 1)2 d[31]
2 upper bound 1654 d(2d
4 upper bound 34 d3  2 d d2 d [10]
number
of
crossings
number of vertices
Greedy
Gr-ran
Mplan
E-len
1-page
Dyn
Bisect
Neural

Figure

6. Heuristic results for complete graphs.
general, exact solutions were feasible only for graphs with up to approximately
50 signicant edges. However, the quality of the initial upper bound is also
very critical to the running time. For example, we were able to process the
cube-connected cycles CCC 4 , with 96 edges, in only 3 cpu seconds due to the
optimality of the heuristic solution (and initial upper bound).
8 Conclusion and Remarks
We have presented several heuristics and an exact algorithm for computing
the xed linear crossing number of a graph. An experimental analysis of their
performance on a variety of test graphs has been given. Our main conclusion
is that a heuristic based on the neural network model of computation is a
highly eective method for solving the problem, giving near-optimal solutions
in most cases and consistently better solutions than other popular heuristics
in other cases. An exact algorithm has been shown eective for graphs with up
to 50 signicant edges, in general, although it can handle much larger graphs
number
of
crossings
number of vertices
Greedy
Gr-ran
Mplan
E-len
1-page
Dyn
Bisect
Neural

Figure

7. Heuristic results for 100 random graphs.
if the initial upper bound is fairly tight.
The algorithms are useful in providing upper bounds to the book crossing
number and planar crossing number of a graph as well as for nding crossing-
minimal 2-page layouts of parallel interconnection networks.
In future work, we plan to study the worst-case performance of the heuristics
and to investigate their adaptation to the unxed linear crossing number
problem. Since this requires nding an optimal vertex ordering on the node
line, the problem complexity is greater than that of FLCNP.
Also, recently some other algorithms have been brought to the attention of
the author, i.e., [46,38], and these may be included along with the present set
of algorithms in future experiments.
number
of
crossings
number of edges
Greedy
Gr-ran
Mplan
E-len
1-page
Dyn
Bisect
Neural

Figure

8. Heuristic results for hypercubic networks.



--R

a competitor for the hypercube?
The book thickness of a graph
A framework for solving VLSI graph layout problems
Embedding graphs in books: a survey
Circulants and their connectivities

A new variation on hypercubes with smaller diameter

Embedding graphs in books: a layout problem with applications to VLSI design
Topological properties of some interconnection network graphs
A neural network algorithm for a graph layout problem

An upper bound to the crossing number of the complete graph drawn on the pages of a book
Algorithms for drawing graphs: an annotated bibliography
An experimental comparison of four graph drawing algorithms
A theoretical network model and the Hamming cube networks
Heuristics for reducing crossings in 2-layered networks
The crossed cube architecture for parallel computation

On the Eggleton and Guy conjectured upper bound for the crossing number of the n-cube

Crossing number of graphs
Latest results on crossing numbers
The toroidal crossing number of the complete graph
Toroidal graphs with arbitrarily high crossing numbers
Kautz and shu


The book thickness of a graph
Introduction to Parallel Algorithms and Architectures: Arrays
Bounds for the crossing number of the n-cube
On the page number of graphs
Crossing minimization in linear embeddings of graphs
A logical calculus of ideas imminent in nervous activity
Permutation procedure for minimising the number of crossings in a network
The cube-connected cycles: a versatile network for parallel computation
IEEE Trans.
Using simulated annealing to
The DIOGENES approach to testable fault-tolerant arrays of processors

On some topological properties of hypercubes




A parallel stochastic optimization algorithm for

Automatic graph drawing and readability of diagrams
Sorting using networks of queues and stacks
Computational aspects of VLSI
Linear and book embeddings of graphs
Four pages are necessary and su-cient for planar graphs
Parallel and Distributed Computing Handbook
--TR
Four pages are necessary and sufficient for planar graphs
Linear and book embeddings of graphs
Embedding graphs in books: a layout problem with applications to VLSI design
Automatic graph drawing and readability of diagrams
Crossing Minimization in Linear Embeddings of Graphs
Bounds for the crossing number of the <italic>N</italic>-cube
Introduction to parallel algorithms and architectures
A new variation on hypercubes with smaller diameter
Graphs with <?Pub Fmt italic>E<?Pub Fmt /italic> edges have pagenumber<inline-equation> <f> <fen lp="par"><rad><rcd><i>E</i></rcd></rad><rp post="par"></fen> </f> </inline-equation> <?Pub Fmt italic>O<?Pub Fmt /italic>
On VLSI layouts of the star graph and related networks
Algorithms for drawing graphs
Parallel and distributed computing handbook
The book crossing number of a graph
Embedding de Bruijn, Kautz and shuffle-exchange networks in books
An experimental comparison of four graph drawing algorithms
CNMGRAFMYAMPERSANDmdash;graphic presentation services for network management
Sorting Using Networks of Queues and Stacks
The cube-connected cycles: a versatile network for parallel computation
Properties and Performance of Folded Hypercubes
The Crossed Cube Architecture for Parallel Computation
A Theoretical Network Model and the Hamming Cube Networks
Book Embeddings and Crossing Numbers
linear layout;neural network;crossing number;branch-and-bound;heuristic