Genetic Algorithms and Book Embeddings: A Dual Layered Approach.
Shannon Overbay, Paul De Palma, Marshall Hurson, Tiffany Arnold, Andrew Pierce · 2012
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.