Abstract
We 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.
References
[1] F. Shahrokhi, O. Sýkora, L.A. Székely, I. Vrt’o, The book crossing number of a graph, J. Graph Theory 21, 413–424, 1996 10.1002/(SICI)1097-0118(199604)21:4<413::AID-JGT7>3.0.CO;2-SSearch in Google Scholar
[2] P.C. Kainen, The book thickness of a graph II, Congressus Numerantium 71, 121–132, 1990 Search in Google Scholar
[3] F. Shahrokhi, O. Sýkora, L.A. Székely, I. Vrt’o, The gap between crossing numbers and the convex crossing numbers, Towards a Theory of Geometric Graphs, In: J. Pach (Ed.), Contemporary Mathematics, 342, American Mathematical Society, Providence, RI USA, 2004, 249–258 10.1090/conm/342/06145Search in Google Scholar
[4] J.M. Six, I.G. Tollis, Circular drawings of biconnected graphs, Proc. of ALENEX’99, LNCS 1619, 57–73, 1999 pp. 57-73. 10.1007/3-540-48518-X_4Search in Google Scholar
[5] M. Masuda, T. Kashiwabara, K. Nakajima, T. Fujisawa, On the NP-completeness of a computer network layout problem, Proc. of IEEE Intl. Symposiumon Circuits and Systems 1987, IEEE Computer Society Press, Los Alamitos, 1987, 292–295 Search in Google Scholar
[6] S. Masuda, T. Kashiwabara, K. Nakajima, T. Fujisawa, Crossing minimization in linear embeddings of graphs, IEEE Trans. Comput. 39, 124–127, 1990 10.1109/12.46286Search in Google Scholar
[7] F.R.K. Chung, F.T. Leighton, A.L. Rosenberg, Diogenes: a methodology for designing fault-tolerant VLSI processor arrays, Proc. the 13th Annu. Symp. Fault-Tolerant Comput, June 1983 Milan, Italy, 26–32 Search in Google Scholar
[8] F.R.K. Chung, F.T. Leighton, A.L. Rosenberg, Embedding graphs in books: a layout problem with applications to VLSI design, SIAM J. Algebra. Discr. 8(1), 33-58, 1987 10.1137/0608002Search in Google Scholar
[9] W.J. Chung, B.S. Smith, S.K. Lim, QCA Physical Design With Crossing Minimization, Proc. IEEE Conference on Nanotechnology, 11-15 July 2005, Nagoya Congress Center Nagoya, Japan, 2005, 262–265 Search in Google Scholar
[10] B.S. Smith, S.K. Lim, QCA Channel Routing With Wire Crossing Minimization, Proc. of The 15th ACM Great Lakes symposiumon VLSI, Chicago, Illinois, USA., 2005, 217–220 10.1145/1057661.1057714Search in Google Scholar
[11] E.Mäkinen, On circular layouts, Int. J. Comput.Math. 24, 29–37, 1988 10.1080/00207168808803629Search in Google Scholar
[12] M. Baur, U. Brandes, Crossing Reduction in Circular Layouts, Proc. 30th Intl. Workshop Graph-Theoretic Concepts in Computer-Science (WG ’04), LNCS 3353, 332–343, 2004 10.1007/978-3-540-30559-0_28Search in Google Scholar
[13] H. He, O. Sýkora, New Circular Drawing Algorihtms, Proc. ITAT’04, 15-19 Sept. 2004, High Tatras, Slovakia, 2004 Search in Google Scholar
[14] A.N. Melikov, V.M. Koreicik, V.A. Tišcenko, Minimization of the number of intersections of edges of a graph (Russian), Vycisl. Sistemy Vyp. 47, 32–40, 1971 Search in Google Scholar
[15] T.A.J. Nicholson, Permutation procedure for minimazing the number of crossings in a network, Proc. Inst. Elec. Engnrs. 115, 21–26, 1968 10.1049/piee.1968.0004Search in Google Scholar
[16] R. Cimikowski, Algorithms for the fixed linear crossing number problem, Discrete App. Math. 122, 93–115, 2002 10.1016/S0166-218X(01)00314-6Search in Google Scholar
[17] W. Winterbach, The crossing number of a graph in the plane, Master’s Thesis, Dept. Appl. Math., University of Stellenbosch, SA, 2005 Search in Google Scholar
[18] E. de Klerk, D.V. Pasechnik, Improved lower bounds for the 2- page crossing numbers of Km,n and Kn via semidefinite programming, http://arxiv.org/abs/1110.4824v1, October 2011. Search in Google Scholar
[19] T. Poranen, E. Mäkinen, H. He, A simulated annealing algorithm for the 2-page crossing number problem, Proc. of the International Network Optimization Conference, 22-25 Apr. 2007, Spa, Belgium, 2007 Search in Google Scholar
[20] H. He, O. Sýkora, E. Mäkinen, Genetic algorithms for the 2-page drawing problem of graphs, J. Heuristics 13(1), 77–93, 2007 10.1007/s10732-006-9000-4Search in Google Scholar
[21] H. He, O. Sýkora, E. Mäkinen, An Improved Neural Network Model for the 2-page Crossing Number Problem, IEEE Trans. Neural Netw. 17(6), 1642–1646, 2006 10.1109/TNN.2006.881486Search in Google Scholar
[22] H. He, O. Sýkora, A. Salagean, Various Island-based Parallel Genetic Algorithms for the 2-page Drawing Problem, Proc. of IASTED International Conference on Parallel and Distributed Computing and Networks, 14-16 February 2006, Innsbruck, Austria (PDCN2006), 2006, 316–323 Search in Google Scholar
[23] H. He, O. Sýkora, A. Salagean, E.Mäkinen, Parallelization of Genetic Algorithm for the 2-page Crossing Number Problem, J. Parall. Distr. Com. 67(2), 229–241, 2007 10.1016/j.jpdc.2006.08.002Search in Google Scholar
[24] GDToolkit: http://www.dia.uniroma3.it/b:24/ Search in Google Scholar
[25] R. Cimikowski, P. Shope, A neural network algorithm for a graph layout problem, IEEE Trans. Neural Netw. 7(2), 341–346, 1996 10.1109/72.485670Search in Google Scholar
[26] W.S. McCulloch, W. Pitts, A logical calculus of the ideas immanent in nervous activity, B. Math. Biophys. 5, 115–133, 1943 10.1007/BF02478259Search in Google Scholar
[27] H. He, A. Salagean, E. Mäkinen, One- and two-page crossing numbers for some types of graphs, International J. Computer Mathematics 87(8), 1667–1679, 2010 10.1080/00207160802524747Search in Google Scholar
[28] R. Fulek, H. He, O. Sýkora, I. Vrt’o, Outerplanar Crossing Numbers of 3-Row Meshes, Halin Graphs and Complete p-Partite Graphs, Proc. SOFSEM’05, LNCS 3381, 376–379, 2005 10.1007/978-3-540-30577-4_43Search in Google Scholar
[29] R.K. Guy, Crossing number of graphs, In Y. Alavi, D.R. Lick, A.T. White (Eds), Graph Theory and Applications: Proc. of the Conference at Western Michigan University, Kalamazoo, Mich., Springer-Verlag, New York, 1972, 111–124 Search in Google Scholar
[30] F. Boesch, R. Tindell,Circulants and their connectivities, J. Graph Theory 8, 487–499, 1984 10.1002/jgt.3190080406Search in Google Scholar
[31] F. Bernhart, P. Kainen,The book thickness of a graph, J. Combin. Theory Ser. B. 27, 320–331, 1979 10.1016/0095-8956(79)90021-2Search in Google Scholar
[32] M. Yannakakis, Four page are neccessary and suffcient for planar graphs (extended abstract), Proc. of the Eighteenth Annual ACM Symposium on Theory of Computing, Berkeley, California, United States, 1986, 104–108 10.1145/12130.12141Search in Google Scholar
[33] J. Adamson, B.R. Richter, Arrangements, circular arrangements and the crossing number of C7 ×Cn, J. Combin. Theory Ser. B 90, 21–39, 2004 10.1016/j.jctb.2003.05.001Search in Google Scholar
[34] L.Y. Glebsky, G. Salazar, The conjecture cr(Cm ×Cn) = (m−2)n is true for all but finitely n, for each m, J. Graph Theory 47, 53–72, 2004 10.1002/jgt.20016Search in Google Scholar
[35] F. Shahrokhi, O. Sýkora, L.A. Székely, I. Vrt’o, Intersection of Curves and Crossing Number of Cm × Cn on Surfaces, Descrete Comput. Geom. 19(2), 237–247, 1998 10.1007/PL00009343Search in Google Scholar
© 2015 H. He et al.
This work is licensed under the Creative Commons Attribution 4.0 International License.
