- No file added yet -

# Sequential and parallel algorithms for low-crossing graph drawing

thesis

posted on 2013-08-14, 13:32 authored by Matthew NewtonThe one- and two-sided bipartite graph drawing problem alms to find a
layout of a bipartite graph, with vertices of the two parts placed on parallel
imaginary lines, that has the minimum number of edge-crossings. Vertices
of one part are in fixed positions for the one-sided problem, whereas all
vertices are free to move along their lines in the two-sided version. Many
different heuristics exist for finding approximations to these problems, which
are NP-hard.
New sequential and parallel methods for producing drawings with low edgecrossings
are investigated and compared to existing algorithms, notably
Penalty Minimisation and Sifting, the current leaders. For the one-sided
problem, new methods that include those based on simple stochastic hillclimbing,
simulated annealing and genet.ic algorithms were tested. The new
block-crossover genetic algorithm produced very good results with lower
crossings than existing methods, although it tended to be slower. However,
time was a secondary aim, the priority being to achieve low numbers of
crossings. This algorithm can also be seeded with the output of an existing
algorithm to improve results; combining with Penalty Minimisation in this
way improved both the speed and number of crossings.
Four parallel methods for the one-sided problem have been created, although
two were abandoned because they gave bad results for even simple graphs.
The other two methods, based on stochastic hill-climbing, produced acceptable
results in faster times than similar sequential methods. PVM was used
as the parallel communication system.
Two new heuristics were studied for the two-sided problem, for which the
only known existing method is to apply one-sided algorithms iteratively.
The first is based on a heuristic for the linear arrangment problem; the
second is a method of performing stochastic hill-climbing on two sides. A way of applying anyone-sided algorithm iteratively was also created. The
linear arrangement method based on the Koren-Harel multi-scale algorithm
achieved the best results, outperforming iterative Barycentre (previously the
best method) and iterative Penalty Minimisation.
Another area of this work created three new heuristics for the k-planar drawing
problem where k > 1. These are the first known practical algorithms
to solve this problem. A sequential genetic algorithm based on TimGA is
devised to work on k-planar graphs. Two parallel algorithms, one island
model and the other a 'mesh' model, are also given. Comparison of results
for k = 2 indicate that the parallel island method is better than the other
two methods. MPI was used for the parallel communication.
Overall, 14 new methods are introduced, of which 10 were developed into
working algorithms. For the one-sided bipartite graph drawing problem
the new block-crossover genetic algorithm can produce drawings with lower
crossings than the current best available algorithms. The parallel methods
do not perform as well as the sequential ones, although they generally
achieved the same results faster.
All of the new two-sided methods worked well; the weighted two-sided swap
stochastic hill-climbing method was comparable to the existing best method,
iterative Barycentre, and generally produced drawings with lower crossings,
although it suffered with needing a good termination condition. The new
methods based on the linear arrangement problem consistently produced
drawings with lower crossings than iterative Barycentre, although they were
nearly always slower.
A new parallel algorithm for the k-planar drawing problem, based on the
island model, generally created drawings with the lowest edge-crossings,
although no algorithms were known to exist to make comparisons.

## History

## School

- Science

## Department

- Computer Science

## Publisher

© Matthew Newton## Publication date

2007## Notes

A Doctoral Thesis. Submitted in partial fulfilment of the requirements for the award of Doctor of Philosophy of Loughborough University## EThOS Persistent ID

uk.bl.ethos.479017## Language

- en