HSM06a.pdf (6.41 MB)
Download file

Genetic algorithms for the 2-page book drawing problem of graphs

Download (6.41 MB)
journal contribution
posted on 25.09.2006, 13:39 authored by Hongmei He, Ondrej Sykora, Erkki Makinen
The minimisation of edge crossings in a book drawing of a graph is one of the important goals for a linear VLSI design, and the 2-page crossing number of a graph provides an upper bound for the standard planar crossing number. We design genetic algorithms for the 2-page drawings, and test them on the benchmark test suits, Rome graphs and Random Connected Graphs. We also test some circulant graphs, and get better results than previously presented in the literature. Moreover, we formalise three conjectures for certain kinds of circulant graphs, supported by our experimental results.

History

School

  • Science

Department

  • Computer Science

Pages

6702231 bytes

Citation

HE, H., SÝKORA, O. and MÄKINEN, E., 2007. Genetic algorithms for the 2-page book drawing problem of graphs. Journal of Heuristics, 13 (1), pp. 77-93

Publisher

© Springer

Version

AM (Accepted Manuscript)

Publication date

2007

Notes

This article will be published in the Journal of Heuristics [© Springer] and will also available at: http://www.springerlink.com/content/1572-9397/

ISSN

1381-1231;1572-9397

Language

en