Algorithms on the Book Crossing Number Problem of Graphs

After reviewing recent research in Graph Drawings, in this book, author investigated: 1) Novel heuristic algorithms to solve the 1-page and 2-page BCNPs. They obtained the results better than or comparable with existing algorithms. 2) Genetic algorithms for the BCNPs. They obtained better results than the latest heuristic algorithms. 3) Two neural network models for the 1-page and 2-page BCNPs, respectively, and the convergence of the neural network models. Both models obtained good results. Especially, the model for the 2-page BCNP achieved much better performance than the existing model. 4) The complexity of parallel genetic algorithms, and the unified framework of PGA models in the form of function PGA (subpopulation size, cluster size, migration period, topology). 5) Theorems about the 1-page and 2-page BCNs for some kinds of structural graphs. 6) Proximity to the optimal crossing numbers for the evaluation of different algorithms on some kinds of structural graphs, and conjectures of 1-page and 2-page BCNs for some kinds of structural graphs.

Dr. Hongmei He is a lecturer in Cranfield University in the UK. She obtained her Ph.D. in Computer Science from Loughborough University in 2006. Her research interests include Optimization, Network Mining, Data Fusion and Cognitive Robotics. Dr. He is a member of IEEE since 2005, and an Editorial Board Member of Advances in Computing since 2011.