Abstract
In this work, we propose the use of two neural models performing jointly in order to minimize the same energy function. This model is focused on obtaining good solutions for the two pages book crossing problem, although some others problems can be efficiently solved by the same model. The neural technique applied to this problem allows to reduce the energy function by changing outputs from both networks –outputs of first network representing location of nodes in the nodes line, while the outputs of the second one meaning the half-plane where the edges are drawn.
Detailed description of the model is presented, and the technique to minimize an energy function is fully described. It has proved to be a very competitive and efficient algorithm, in terms of quality of solutions and computational time, when compared to the state-of-the-art methods. Some simulation results are presented in this paper, to show the comparative efficiency of the methods.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Chinn, P.Z., Chvátalová, L., Dewdney, A.K., Gibbs, N.E.: The bandwidth problem for graphs and matrices – a survey. J. Graph Theory 6, 223–253 (1982)
Kainen, P.C.: The book thickness of a graph, ii. Congr. Numer. 71, 127–132 (1990)
Chung, F.R.K., Leighton, F.T., Rosenberg, A.L.: Embedding graphs in books: a layout problem with applications to vlsi design. SIAM J. Alg. Disc. Meth. 8, 33–58 (1987)
Malitz, S.M.: On the page number of graphs. J. Algorithms 17, 71–84 (1994)
Ullman, J.D.: Computational Aspects of VLSI. Computer Science Press, Los Alamitos (1984)
Raghavan, R., Sahni, S.: Single row routing. IEEE Trans. Comput. C-32, 209–220 (1983)
Sinden, F.W.: Topology of thin films circuit. Bell Syst. Tech. Jour. XLV, 1639–1666 (1966)
Tamassia, R., Di Battista, G., Batini, C.: Automatic graph drawing and readability of diagrams. IEEE Trans. Syst. Man. Cybern. 18, 61–79 (1988)
Cimikowski, R.: Algorithms for the fixed linear crossing number problem. Discrete Applied Mathematics 122, 93 (2002)
Nicholson, T.A.J.: Permutation procedure for minimising the number of crossings in a network. Proc. IEE 115, 21–26 (1968)
Garey, M.R., Johnson, D.S.: Crossing number is np-complete. SIAM J. Alg. Disc. Methods 4, 312–316 (1983)
Masuda, S., Nakajima, K., Kashiwabara, T., Fujisawa, T.: Crossing minimization in linear embeddings of graphs. IEEE Trans. Comput. 39, 124–127 (1990)
Cimikowski, R., Shope, P.: A neural-network algorithm for a graph layout problem. IEEE Transactions on Neural Networks 7, 341–345 (1996)
Takefuji, Y.: Design of parallel distributed cauchy machines. In: Proc. Int. Joint Conf. Neural Networks, pp. 529–536 (1989)
Takefuji, Y.: Neural Network Parallel Computing. Kluwer Academic Publishers, Dordrecht (1992)
Mérida-Casermeiro, E., Galán-Marín, G., Muñoz Pérez, J.: An efficient multivalued hopfield network for the travelling salesman problem. Neural Processing Letters 14, 203–216 (2001)
Mérida-Casermeiro, E., Muñoz Pérez, J., Domínguez-Merino, E.: An n-parallel multivalued network: Applications to the travelling salesman problem. In: Mira, J., Álvarez, J.R. (eds.) IWANN 2003. LNCS, vol. 2686, pp. 406–413. Springer, Heidelberg (2003)
Mérida-Casermeiro, E., López-Rodríguez, D.: Graph partitioning via recurrent multivalued neural networks. In: Cabestany, J., Prieto, A.G., Sandoval, F. (eds.) IWANN 2005. LNCS, vol. 3512, pp. 1149–1156. Springer, Heidelberg (2005)
López-Rodríguez, D., Mérida-Casermeiro, E., Ortiz-de-Lazcano-Lobato, J.M., López-Rubio, E.: Image Compression by Vector Quantization with Recurrent Discrete Networks. In: Kollias, S., Stafylopatis, A., Duch, W., Oja, E. (eds.) ICANN 2006. LNCS, vol. 4132, pp. 595–605. Springer, Heidelberg (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
López-Rodríguez, D., Mérida-Casermeiro, E., Ortíz-de-Lazcano-Lobato, J.M., Galán-Marín, G. (2007). Two Pages Graph Layout Via Recurrent Multivalued Neural Networks. In: Sandoval, F., Prieto, A., Cabestany, J., Graña, M. (eds) Computational and Ambient Intelligence. IWANN 2007. Lecture Notes in Computer Science, vol 4507. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73007-1_24
Download citation
DOI: https://doi.org/10.1007/978-3-540-73007-1_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73006-4
Online ISBN: 978-3-540-73007-1
eBook Packages: Computer ScienceComputer Science (R0)