{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,4]],"date-time":"2024-12-04T05:24:59Z","timestamp":1733289899030,"version":"3.30.1"},"reference-count":53,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[2002,10,1]],"date-time":"2002-10-01T00:00:00Z","timestamp":1033430400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3942,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2002,10]]},"DOI":"10.1016\/s0166-218x(01)00314-6","type":"journal-article","created":{"date-parts":[[2002,10,14]],"date-time":"2002-10-14T15:12:20Z","timestamp":1034608340000},"page":"93-115","source":"Crossref","is-referenced-by-count":20,"title":["Algorithms for the fixed linear crossing number problem"],"prefix":"10.1016","volume":"122","author":[{"given":"Robert","family":"Cimikowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(01)00314-6_BIB1","series-title":"Hypercube and Distributed Computers","article-title":"De Bruijn and Kautz networks: a competitor for the hypercube?","author":"Bermond","year":"1989"},{"key":"10.1016\/S0166-218X(01)00314-6_BIB2","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1016\/0095-8956(79)90021-2","article-title":"The book thickness of a graph","volume":"27","author":"Bernhart","year":"1979","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/S0166-218X(01)00314-6_BIB3","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","article-title":"A framework for solving VLSI graph layout problems","volume":"28","author":"Bhatt","year":"1984","journal-title":"J. Comput. Systems Sci."},{"issue":"2","key":"10.1016\/S0166-218X(01)00314-6_BIB4","first-page":"134","article-title":"Embedding graphs in books: a survey","volume":"139","author":"Bilski","year":"1992","journal-title":"IEE Proc. E"},{"key":"10.1016\/S0166-218X(01)00314-6_BIB5","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1002\/jgt.3190080406","article-title":"Circulants and their connectivities","volume":"8","author":"Boesch","year":"1984","journal-title":"J. Graph Theory"},{"year":"1985","series-title":"Random Graphs","author":"Bollob\u00e1s","key":"10.1016\/S0166-218X(01)00314-6_BIB6"},{"key":"10.1016\/S0166-218X(01)00314-6_BIB7","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/0020-0190(93)90065-H","article-title":"A new variation on hypercubes with smaller diameter","volume":"46","author":"Chedid","year":"1993","journal-title":"Inform. Proc. Lett."},{"key":"10.1016\/S0166-218X(01)00314-6_BIB8","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1002\/jgt.3190060302","article-title":"The bandwidth problem for graphs and matrices\u2014a survey","volume":"6","author":"Chinn","year":"1982","journal-title":"J. Graph Theory"},{"key":"10.1016\/S0166-218X(01)00314-6_BIB9","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/0608002","article-title":"Embedding graphs in books: a layout problem with applications to VLSI design","volume":"8","author":"Chung","year":"1987","journal-title":"SIAM J. Algebra Discrete Methods"},{"key":"10.1016\/S0166-218X(01)00314-6_BIB10","first-page":"19","article-title":"Topological properties of some interconnection network graphs","volume":"121","author":"Cimikowski","year":"1996","journal-title":"Congr. Numer."},{"issue":"2","key":"10.1016\/S0166-218X(01)00314-6_BIB11","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1109\/72.485670","article-title":"A neural network algorithm for a graph layout problem","volume":"7","author":"Cimikowski","year":"1996","journal-title":"IEEE Trans. Neural Networks"},{"key":"10.1016\/S0166-218X(01)00314-6_BIB12","first-page":"758","article-title":"A combinatorial problem","volume":"49","author":"de Bruijn","year":"1946","journal-title":"Nederl. Akad. Wetensch. Proc. Ser. A."},{"issue":"1\u20132","key":"10.1016\/S0166-218X(01)00314-6_BIB13","first-page":"75","article-title":"An upper bound to the crossing number of the complete graph drawn on the pages of a book","volume":"19","author":"Damiani","year":"1994","journal-title":"J. Combin. Inform. System Sci."},{"key":"10.1016\/S0166-218X(01)00314-6_BIB14","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0925-7721(94)00014-X","article-title":"Algorithms for drawing graphs: an annotated bibliography","volume":"4","author":"Di Battista","year":"1994","journal-title":"Comput. Geom."},{"issue":"5,6","key":"10.1016\/S0166-218X(01)00314-6_BIB15","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/S0925-7721(96)00005-3","article-title":"An experimental comparison of four graph drawing algorithms","volume":"7","author":"Di Battista","year":"1997","journal-title":"Comput. Geom."},{"key":"10.1016\/S0166-218X(01)00314-6_BIB16","doi-asserted-by":"crossref","unstructured":"S.K. Das, A. Mao, A theoretical network model and the Hamming cube networks, Proceedings of the Eigth International IEEE Parallel Processing Symposium, Cancun, Mexico, 1996, pp. 18\u201322.","DOI":"10.1109\/IPPS.1994.288324"},{"key":"10.1016\/S0166-218X(01)00314-6_BIB17","first-page":"89","article-title":"Heuristics for reducing crossings in 2-layered networks","volume":"21-A","author":"Eades","year":"1986","journal-title":"Ars Combin."},{"issue":"5","key":"10.1016\/S0166-218X(01)00314-6_BIB18","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1109\/71.159036","article-title":"The crossed cube architecture for parallel computation","volume":"3","author":"Efe","year":"1992","journal-title":"IEEE Trans. Parallel & Distrib. Systems"},{"issue":"1","key":"10.1016\/S0166-218X(01)00314-6_BIB19","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1109\/71.80187","article-title":"Properties and performance of folded hypercubes","volume":"2","author":"El-Amawy","year":"1991","journal-title":"IEEE Trans. Parallel & Distrib. Systems"},{"key":"10.1016\/S0166-218X(01)00314-6_BIB20","first-page":"271","article-title":"On the Eggleton and Guy conjectured upper bound for the crossing number of the n-cube","volume":"50","author":"Faria","year":"2000","journal-title":"Math. Slovaca"},{"key":"10.1016\/S0166-218X(01)00314-6_BIB21","doi-asserted-by":"crossref","unstructured":"R.S. Gilbert, W.K. Klein\u00f6der, CNMgraf\u2014graphic presentation services for network management, Proceedings of the Nineth Symposium on Data Communication, Vancouver, BC, Canada, 1985, pp. 199\u2013206.","DOI":"10.1145\/319056.319049"},{"year":"1972","series-title":"Crossing number of graphs, Graph Theory and Applications","author":"Guy","key":"10.1016\/S0166-218X(01)00314-6_BIB22"},{"year":"1971","series-title":"Latest results on crossing numbers, Recent Trends in Graph Theory","author":"Guy","key":"10.1016\/S0166-218X(01)00314-6_BIB23"},{"key":"10.1016\/S0166-218X(01)00314-6_BIB24","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1016\/S0021-9800(68)80063-8","article-title":"The toroidal crossing number of the complete graph","volume":"4","author":"Guy","year":"1968","journal-title":"J. Combin. Theory"},{"key":"10.1016\/S0166-218X(01)00314-6_BIB25","first-page":"58","article-title":"Toroidal graphs with arbitrarily high crossing numbers","volume":"6","author":"Harary","year":"1973","journal-title":"Nanta Math."},{"key":"10.1016\/S0166-218X(01)00314-6_BIB26","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/S0166-218X(97)00009-7","article-title":"Embedding de Bruijn, Kautz and shuffle-exchange networks in books","volume":"78","author":"Hasunuma","year":"1997","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(01)00314-6_BIB27","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF00339943","article-title":"Neural computation of decisions in optimization problems","volume":"52","author":"Hopfield","year":"1985","journal-title":"Biol. Cybernet."},{"issue":"1","key":"10.1016\/S0166-218X(01)00314-6_BIB28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00001","article-title":"2-layer straightline crossing minimization: performance of exact and heuristic algorithms","volume":"1","author":"J\u00fcnger","year":"1997","journal-title":"J. Graph Algorithms Appl."},{"key":"10.1016\/S0166-218X(01)00314-6_BIB29","first-page":"127","article-title":"The book thickness of a graph, II","volume":"71","author":"Kainen","year":"1990","journal-title":"Congr. Numer."},{"year":"1992","series-title":"Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes","author":"Leighton","key":"10.1016\/S0166-218X(01)00314-6_BIB30"},{"key":"10.1016\/S0166-218X(01)00314-6_BIB31","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1002\/jgt.3190150109","article-title":"Bounds for the crossing number of the n-cube","volume":"15","author":"Madej","year":"1991","journal-title":"J. Graph Theory"},{"issue":"1","key":"10.1016\/S0166-218X(01)00314-6_BIB32","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1006\/jagm.1994.1027","article-title":"On the page number of graphs","volume":"17","author":"Malitz","year":"1994","journal-title":"J. Algorithms"},{"issue":"1","key":"10.1016\/S0166-218X(01)00314-6_BIB33","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1109\/12.46286","article-title":"Crossing minimization in linear embeddings of graphs","volume":"39","author":"Masuda","year":"1990","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0166-218X(01)00314-6_BIB34","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BF02478259","article-title":"A logical calculus of ideas imminent in nervous activity","volume":"5","author":"McCulloch","year":"1943","journal-title":"Bull. Math. Biophys."},{"issue":"1","key":"10.1016\/S0166-218X(01)00314-6_BIB35","first-page":"21","article-title":"Permutation procedure for minimising the number of crossings in a network","volume":"115","author":"Nicholson","year":"1968","journal-title":"Proc. IEE"},{"issue":"5","key":"10.1016\/S0166-218X(01)00314-6_BIB36","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1145\/358645.358660","article-title":"The cube-connected cycles: a versatile network for parallel computation","volume":"24","author":"Preparata","year":"1981","journal-title":"Comm. ACM"},{"issue":"3","key":"10.1016\/S0166-218X(01)00314-6_BIB37","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1109\/TC.1983.1676213","article-title":"Single row routing","volume":"C-32","author":"Raghavan","year":"1983","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0166-218X(01)00314-6_BIB38","unstructured":"M. Ringenburg, Using simulated annealing to find crossing numbers, (www.dartmouth.edu\/mfr\/xnum.html)."},{"issue":"10","key":"10.1016\/S0166-218X(01)00314-6_BIB39","doi-asserted-by":"crossref","first-page":"902","DOI":"10.1109\/TC.1983.1676134","article-title":"The DIOGENES approach to testable fault-tolerant arrays of processors","volume":"C-32","author":"Rosenberg","year":"1983","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0166-218X(01)00314-6_BIB40","series-title":"Intuitive Geometry","first-page":"179","article-title":"Crossing numbers: bounds and applications","volume":"Vol. 6","author":"Shahrokhi","year":"1997"},{"key":"10.1016\/S0166-218X(01)00314-6_BIB41","doi-asserted-by":"crossref","unstructured":"A. Sen, A. Sengupta, S. Bandyopadhyay, On some topological properties of hypercubes, incomplete hypercubes, and supercubes, Proceedings of the Seventh International Parallel Processing Symposium, Newport Beach, CA, April, 1993.","DOI":"10.1109\/IPPS.1993.262806"},{"issue":"4","key":"10.1016\/S0166-218X(01)00314-6_BIB42","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1002\/(SICI)1097-0118(199604)21:4<413::AID-JGT7>3.0.CO;2-S","article-title":"The book crossing number of a graph","volume":"21","author":"Shahrokhi","year":"1996","journal-title":"J. Graph Theory"},{"key":"10.1016\/S0166-218X(01)00314-6_BIB43","doi-asserted-by":"crossref","unstructured":"F. Shahrokhi, O. S\u00fdkora, L.A. Sz\u00e9kely, I. Vrt\u0306o, Book embeddings and crossing number, Proceedings of the 20th International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201994), Lecture Notes in Computer Science, Vol. 903, Springer, Berlin, 1995, pp. 256\u2013268.","DOI":"10.1007\/3-540-59071-4_53"},{"key":"10.1016\/S0166-218X(01)00314-6_BIB44","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/BF01989746","article-title":"On crossing numbers of hypercubes and cube-connected cycles","volume":"33","author":"S\u00fdkora","year":"1993","journal-title":"BIT"},{"key":"10.1016\/S0166-218X(01)00314-6_BIB45","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0167-9260(94)90021-3","article-title":"On VLSI layouts of the star graph and related networks, integration","volume":"17","author":"S\u00fdkora","year":"1994","journal-title":"The VLSI J."},{"key":"10.1016\/S0166-218X(01)00314-6_BIB46","first-page":"135","article-title":"A parallel stochastic optimization algorithm for finding mappings of the rectilinear minimal crossing problem","volume":"43","author":"Thorpe","year":"1996","journal-title":"Ars Combin."},{"key":"10.1016\/S0166-218X(01)00314-6_BIB47","doi-asserted-by":"crossref","first-page":"1221","DOI":"10.1126\/science.245.4923.1221","article-title":"A near-optimum parallel planarization algorithm","volume":"245","author":"Takefuji","year":"1989","journal-title":"Science"},{"key":"10.1016\/S0166-218X(01)00314-6_BIB48","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1109\/21.87055","article-title":"Automatic graph drawing and readability of diagrams","volume":"18","author":"Tamassia","year":"1988","journal-title":"IEEE Trans. Systems Man and Cybernet."},{"key":"10.1016\/S0166-218X(01)00314-6_BIB49","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/321694.321704","article-title":"Sorting using networks of queues and stacks","volume":"19","author":"Tarjan","year":"1972","journal-title":"J. Assoc. Comput. Mach."},{"year":"1984","series-title":"Computational Aspects of VLSI","author":"Ullman","key":"10.1016\/S0166-218X(01)00314-6_BIB50"},{"key":"10.1016\/S0166-218X(01)00314-6_BIB51","doi-asserted-by":"crossref","unstructured":"M. Yannakakis, Linear and book embeddings of graphs, in: Proceedings of the Aegean Workshop on Computing, Lecture Notes in Computer Science, Vol. 227, Springer, Berlin, 1986, pp. 229\u2013240.","DOI":"10.1007\/3-540-16766-8_20"},{"key":"10.1016\/S0166-218X(01)00314-6_BIB52","doi-asserted-by":"crossref","unstructured":"M. Yannakakis, Four pages are necessary and sufficient for planar graphs, Proceedings of the 18th Annual ACM Symposium on Theory of Computers, 1986, pp. 104\u2013108.","DOI":"10.1145\/12130.12141"},{"year":"1996","series-title":"Parallel and Distributed Computing Handbook","author":"Zomaya","key":"10.1016\/S0166-218X(01)00314-6_BIB53"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X01003146?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X01003146?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,3]],"date-time":"2024-12-03T15:58:24Z","timestamp":1733241504000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X01003146"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,10]]},"references-count":53,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2002,10]]}},"alternative-id":["S0166218X01003146"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(01)00314-6","relation":{},"ISSN":["0166-218X"],"issn-type":[{"type":"print","value":"0166-218X"}],"subject":[],"published":{"date-parts":[[2002,10]]}}}