In this WWW page we show some of of the solutions delivered by each heuristic discussed in the paper. These have been obtained by running the different algorithms on the

airfoil1graph, for which we have information on the coordinates of its nodes. By painting its edges in different colors according to their individual cost, the viewer can have a visual idea on the power and limitations of each heuristic method.Edges are painted in the following way: red edges have a cost greter than 250; orange edges have cost between 100 and 250; green edges have a cost between 50 and 100; and blue edges have at most cost 50. The cost of an edge

e=uvin a layoutfcorresponds to |f(u)-f(v)|.

Please click on the pictures to see them in full size!

The original graph:airfoil1is made up of 4253 nodes, 12289 edges and has diameter 64. This graph is a mesh used in FE methods. The best layout found in this layout has cost 285231.A random layout.

Cost: 17174118

The normal layout.

Cost: 407921

The successive augmentation heuristic with a random initial ordering of nodes.(gre)

Cost: 11755558

The successive augmentation heuristic with a random-breadth initial ordering of nodes.(rbs)

Cost: 2408682

The successive augmentation heuristic with a breadth-first search initial ordering of nodes.(bfs)

Cost: 713039

The successive augmentation heuristic with a depth-first search initial ordering of nodes.(dfs)

Cost: 741733

Hillclimbing on the FlipE neighborhood.(hillcE)

Cost: 10781712

Hillclimbing on the Flip2 neighborhood.(hillc2)

Cost: 1191184

Hillclimbing on the Flip3 neighborhood.(hillc3)

Cost: 1933272

Spectral sequencing.(spec)

Cost: 352682

Three phases of simulated annealing (sa) [begining, middle, end].

Final cost: 292777