He, HongmeiSălăgean, AnaMäkinen, ErkkiVrt'o, Imrich2017-11-032017-11-032015-08-13He H, Salagean A, Makinen E, Vrt’o I, Various heuristic algorithms for the two-page drawing problem of graphs, Open Computer Science, Vol. 5, Issue 1, August 2015, pp. 22-402299-1093http://dx.doi.org/10.1515/comp-2015-0004https://dspace.lib.cranfield.ac.uk/handle/1826/12700We propose several new heuristics for the twopage book crossing problem, which are based on recent algorithms for the corresponding one-page problem. Especially, the neural network model for edge allocation is combined for the first time with various one-page algorithms. We investigate the performance of the new heuristics by testing them on various benchmark test suites. It is found out that the new heuristics outperform the previously known heuristics and produce good approximations of the planar crossing number for severalwell-known graph families. We conjecture that the optimal two-page drawing of a graph represents the planar drawing of the graph.enAttribution-Non-Commercial-No Derivatives 3.0 Unported (CC BY-NC-ND 3.0). You are free to: Share — copy and redistribute the material in any medium or format. The licensor cannot revoke these freedoms as long as you follow the license terms. Under the following terms: Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use. Information: Non-Commercial — You may not use the material for commercial purposes. No Derivatives — If you remix, transform, or build upon the material, you may not distribute the modified material. No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.Heuristic algorithmTwo-page book crossing numberOne-page book crossing numberHamiltonian cyclePlanar drawingArticle