HS04.pdf (232.21 kB)
Genetic algorithms for bipartite and outerplanar graph drawings are best!
book
posted on 2006-09-27, 16:15 authored by Hongmei He, Matthew Newton, Ondrej SykoraWe design genetic algorithms with small populations for two
basic problems of graph drawing: the one-sided bipartite drawing and the
outerplanar drawing. We compare our results for the one-sided bipartite
drawing problem with Penalty Minimisation (PM)[3], the best one-sided
heuristic currently available. For graphs without a structural symmetry,
our genetic algorithm achieves drawings with lower numbers of crossings
than PM. If run on different initial random seeds and for a longer time, we
can achieve same results as PM for graphs with a symmetrical structure.
We compare performance of our genetic algorithm for the outerplanar
drawing with the previously known best heuristic algorithms such as [2]
and [7] on more important suites of graphs and get better results.
History
School
- Science
Department
- Computer Science
Pages
215163 bytesCitation
HE, NEWTON and SÝKORA, 2005. Genetic algorithms for bipartite and outerplanar graph drawings are best! IN: Communications of the 31st Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2005), Liptovsky Jan, Slovakia, 22-28 JanuaryPublication date
2005Notes
This is a conference paperLanguage
- en