Genetic algorithms and book embeddings: A dual layered approach

The genetic algorithm (GA) has been applied to a wide variety of problems where truly optimal solutions are computationally intractable. One such problem is the book embedding problem from graph theory. A book embedding is an ordering of vertices along a line (the spine) with the edges embedded in half-planes (the pages) extruding from the line so that the edges do not cross. The goal is to find the minimal number of halfplanes needed to embed a given graph. This problem is known to be NP-complete. The paper shows that the GA can be used to generate counter-examples to conjectured minimum bounds.