HSM06a.pdf (6.41 MB)
Download fileGenetic algorithms for the 2-page book drawing problem of graphs
journal contribution
posted on 2006-09-25, 13:39 authored by Hongmei He, Ondrej Sykora, Erkki MakinenThe 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