{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,3]],"date-time":"2023-01-03T07:51:49Z","timestamp":1672732309523},"reference-count":37,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2000,8,1]],"date-time":"2000-08-01T00:00:00Z","timestamp":965088000000},"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":4733,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2000,8]]},"DOI":"10.1016\/s0304-3975(99)00285-6","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T14:08:42Z","timestamp":1027606122000},"page":"281-294","source":"Crossref","is-referenced-by-count":7,"title":["A new lower bound for the bipartite crossing number with applications"],"prefix":"10.1016","volume":"245","author":[{"given":"Farhad","family":"Shahrokhi","sequence":"first","affiliation":[]},{"given":"Ondrej","family":"S\u00fdkora","sequence":"additional","affiliation":[]},{"given":"L\u00e1szl\u00f3 A.","family":"Sz\u00e9kely","sequence":"additional","affiliation":[]},{"given":"Imrich","family":"Vrt'o","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(99)00285-6_BIB1","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0893-9659(95)00015-I","article-title":"Edge isoperimetric theorems for integer point arrays","volume":"8","author":"Ahlswede","year":"1995","journal-title":"Appl. Math. Lett."},{"key":"10.1016\/S0304-3975(99)00285-6_BIB2","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","article-title":"A framework for solving VLSI layout problems","volume":"28","author":"Bhatt","year":"1984","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(99)00285-6_BIB3","series-title":"Combinatorics, Ch. 16","author":"Bollob\u00e1s","year":"1986"},{"key":"10.1016\/S0304-3975(99)00285-6_BIB4","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/BF01275667","article-title":"Edge-isoperimetric inequalities in the grid","volume":"11","author":"Bollob\u00e1s","year":"1991","journal-title":"Combinatorica"},{"key":"10.1016\/S0304-3975(99)00285-6_BIB5","doi-asserted-by":"crossref","unstructured":"B. Bollob\u00e1s, I. Leader, Matchings and paths in cubes, Discrete Appl. Math. 75 (1997) 1\u20138.","DOI":"10.1016\/S0166-218X(96)00076-5"},{"key":"10.1016\/S0304-3975(99)00285-6_BIB6","unstructured":"F.J. Brandenburg, M. J\u00fcnger, P. Mutzel, Algorithms for automatic graph drawing, Technical Report, Max Planck Institute, MPI-I-97-1-007, Saarbr\u00fccken, March 1997 (in German)."},{"key":"10.1016\/S0304-3975(99)00285-6_BIB7","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1109\/21.364865","article-title":"The assignment heuristics for crossing reduction","volume":"25","author":"Catarci","year":"1995","journal-title":"IEEE Trans. Systems Man Cybernet."},{"key":"10.1016\/S0304-3975(99)00285-6_BIB8","series-title":"Spectral Graph Theory, Regional Conference Series in Mathematics Number, vol. 92","author":"Chung","year":"1997"},{"key":"10.1016\/S0304-3975(99)00285-6_BIB9","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1016\/0097-3165(88)90034-9","article-title":"On induced subgraphs of the cube","volume":"49","author":"Chung","year":"1988","journal-title":"J. Combin. Theory (A)"},{"key":"10.1016\/S0304-3975(99)00285-6_BIB10","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":"Discrete Comput. Geometry"},{"key":"10.1016\/S0304-3975(99)00285-6_BIB11","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/BF01187020","article-title":"Edge crossings in drawings of bipartite graphs","volume":"11","author":"Eades","year":"1994","journal-title":"Algorithmica"},{"key":"10.1016\/S0304-3975(99)00285-6_BIB12","doi-asserted-by":"crossref","first-page":"52","DOI":"10.2307\/2319261","article-title":"Crossing number problems","volume":"80","author":"Erd\u0151s","year":"1973","journal-title":"Amer. Math. Monthly"},{"key":"10.1016\/S0304-3975(99)00285-6_BIB13","unstructured":"G. Even, J.S. Naor, S. Rao, B. Schieber, Fast approximate graph partition algorithms, in: Proc. 8th Annual ACM-SIAM Symp. on Disc. Algo., 1997, pp. 639\u2013648."},{"key":"10.1016\/S0304-3975(99)00285-6_BIB14","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1137\/0604033","article-title":"Crossing number is NP-complete","volume":"4","author":"Garey","year":"1983","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"10.1016\/S0304-3975(99)00285-6_BIB15","doi-asserted-by":"crossref","unstructured":"M. Hansen, Approximate algorithms for geometric embeddings in the plane with applications parallel processing problems, in Proc. 30th Annual ACM Symp. on Theory of Computing, 1989, pp. 604\u2013609.","DOI":"10.1109\/SFCS.1989.63542"},{"key":"10.1016\/S0304-3975(99)00285-6_BIB16","doi-asserted-by":"crossref","first-page":"146","DOI":"10.2307\/2689132","article-title":"Determinants, permanents and bipartite graphs","volume":"42","author":"Harary","year":"1969","journal-title":"Math. Mag."},{"key":"10.1016\/S0304-3975(99)00285-6_BIB17","first-page":"203","article-title":"A new crossing number for bipartite graphs","volume":"1","author":"Harary","year":"1972","journal-title":"Utilitas Math."},{"key":"10.1016\/S0304-3975(99)00285-6_BIB18","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1137\/0112012","article-title":"Optimal assignments of numbers to vertices","volume":"12","author":"Harper","year":"1964","journal-title":"SIAM J. Appl. Math."},{"key":"10.1016\/S0304-3975(99)00285-6_BIB19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00001","article-title":"2-layer straight line crossing minimization: performance of exact and heuristic algorithms","volume":"1","author":"J\u00fcnger","year":"1997","journal-title":"J. Graph Algorithms Appl."},{"key":"10.1016\/S0304-3975(99)00285-6_BIB20","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0166-218X(92)90229-4","article-title":"Optimal linear labelings and eigenvalues of graphs","volume":"36","author":"Juvan","year":"1992","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0304-3975(99)00285-6_BIB21","series-title":"Complexity Issues in VLSI","author":"Leighton","year":"1983"},{"key":"10.1016\/S0304-3975(99)00285-6_BIB22","doi-asserted-by":"crossref","unstructured":"F.T. Leighton, S. Rao, An approximate max flow min cut theorem for multicommodity flow problem with applications to approximation algorithm, in: Proc. 29th Foundation of Computer Science, IEEE Computer Society Press, Washington, DC 1988, pp. 422\u2013431.","DOI":"10.1109\/SFCS.1988.21958"},{"key":"10.1016\/S0304-3975(99)00285-6_BIB23","series-title":"Combinatorial Algorithms for Integrated Circuit Layouts","author":"Lengauer","year":"1990"},{"key":"10.1016\/S0304-3975(99)00285-6_BIB24","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1016\/S0377-2217(97)00291-9","article-title":"A tabu search algorithm for the bipartite drawing problem","volume":"106","author":"Mart\u0131\u0301","year":"1998","journal-title":"European J. Oper. Res."},{"key":"10.1016\/S0304-3975(99)00285-6_BIB25","first-page":"85","article-title":"On the bipartite crossing number","volume":"17","author":"May","year":"1988","journal-title":"Control and Cybern."},{"key":"10.1016\/S0304-3975(99)00285-6_BIB26","first-page":"21","article-title":"Minimal numberings of vertices of a rectangular lattice","volume":"70","author":"Muradyan","year":"1980","journal-title":"Akad. Nauk Armjan. SSR Doklady"},{"key":"10.1016\/S0304-3975(99)00285-6_BIB27","doi-asserted-by":"crossref","unstructured":"P. Mutzel, An alternative method to crossing minimization on hierarchial graphs, Proc. Graph Drawing \u201996, Lecture Notes in Computer Science, Springer, Berlin, 1997, pp. 318\u2013333.","DOI":"10.1007\/3-540-62495-3_57"},{"key":"10.1016\/S0304-3975(99)00285-6_BIB28","series-title":"Combinatorial Geometry","author":"Pach","year":"1995"},{"key":"10.1016\/S0304-3975(99)00285-6_BIB29","series-title":"An Introduction to VLSI Physical Design","author":"Sarrafzadeh","year":"1995"},{"key":"10.1016\/S0304-3975(99)00285-6_BIB30","doi-asserted-by":"crossref","unstructured":"F. Shahrokhi, O. S\u00fdkora, L.A. Sz\u00e9kely, I. Vrt'o, On bipartite crossings, biplanar subgraphs, and the linear arrangement problem, in: Proc. 5th Workshop on Algorithms and Data Structures, (WADS\u201997), August 6\u20138, 1997 Halifax, Nova Scotia, Canada, Lecture Notes in Computer Science, vol. 1272, Springer, Berlin, 1997, pp. 55\u201368. (Extended version submitted to a journal.)","DOI":"10.1007\/3-540-63307-3_48"},{"key":"10.1016\/S0304-3975(99)00285-6_BIB31","doi-asserted-by":"crossref","unstructured":"F. Shahrokhi, O. S\u00fdkora, L.A. Sz\u00e9kely, I. Vrt'o, Bipartite crossing numbers of meshes and hypercubes, in: Proc. Graph Drawing, (GD\u201997), September 18\u201320, 1997 Rome, Italy, Lecture Notes in Computer Science, vol. 1353, Springer, Berlin, 1997, pp. 37\u201346.","DOI":"10.1007\/3-540-63938-1_48"},{"key":"10.1016\/S0304-3975(99)00285-6_BIB32","unstructured":"F. Shahrokhi, O. S\u00fdkora, L.A. Sz\u00e9kely, I. Vrt'o, Crossing numbers: bounds and applications, in: Intuitive Geometry I. B\u00e1r\u00e1ny, K. B\u00f6r\u00f6czky (Eds.), Bolyai Society Mathematical Studies 6, 1997, pp. 179\u2013206."},{"key":"10.1016\/S0304-3975(99)00285-6_BIB33","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/S0166-218X(87)80003-3","article-title":"Bipartite permutation graphs","volume":"19","author":"Spinrad","year":"1987","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0304-3975(99)00285-6_BIB34","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1109\/TSMC.1981.4308636","article-title":"Methods for visual understanding of hierarchical systems structures","volume":"11","author":"Sugiyama","year":"1981","journal-title":"IEEE Trans. Systems Man Cybernet."},{"key":"10.1016\/S0304-3975(99)00285-6_BIB35","series-title":"Graph Theory","author":"Tutte","year":"1984"},{"key":"10.1016\/S0304-3975(99)00285-6_BIB36","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1109\/TSMC.1977.4309760","article-title":"Crossing theory and hierarchy mapping","volume":"7","author":"Warfield","year":"1977","journal-title":"IEEE Trans. Systems Man Cybernet."},{"key":"10.1016\/S0304-3975(99)00285-6_BIB37","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1111\/j.1749-6632.1970.tb56499.x","article-title":"A special crossing number for bipartite graphs: a research problem","volume":"175","author":"Watkins","year":"1970","journal-title":"Ann New York Acad. Sci."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397599002856?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397599002856?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,1,9]],"date-time":"2020-01-09T00:51:10Z","timestamp":1578531070000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397599002856"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,8]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2000,8]]}},"alternative-id":["S0304397599002856"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(99)00285-6","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2000,8]]}}}