{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:54:07Z","timestamp":1725558847121},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540245285"},{"type":"electronic","value":"9783540318439"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/978-3-540-31843-9_36","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T16:54:14Z","timestamp":1278348854000},"page":"360-370","source":"Crossref","is-referenced-by-count":1,"title":["New Exact Results and Bounds for Bipartite Crossing Numbers of Meshes"],"prefix":"10.1007","author":[{"given":"Matthew C.","family":"Newton","sequence":"first","affiliation":[]},{"given":"Ondrej","family":"S\u00fdkora","sequence":"additional","affiliation":[]},{"given":"Martin","family":"U\u017eovi\u010d","sequence":"additional","affiliation":[]},{"given":"Imrich","family":"Vrt\u2019o","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"36_CR1","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1137\/1020084","volume":"20","author":"F.R.K. Chung","year":"1978","unstructured":"Chung, F.R.K.: A conjectured minimum valuation tree. SIAM Review\u00a020, 601\u2013604 (1978)","journal-title":"SIAM Review"},{"key":"36_CR2","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Finocchi, I.: Removing cycles for minimizing crossings. ACM Journal of Experimental Algorithms\u00a06 (2001)","DOI":"10.1145\/945394.945396"},{"key":"36_CR3","series-title":"Algorithms for the Visualization of Graphs","volume-title":"Graph Drawing","author":"J. Battista Di","year":"1999","unstructured":"Di Battista, J., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Algorithms for the Visualization of Graphs. Prentice-Hall, Englewood Cliffs (1999)"},{"key":"36_CR4","doi-asserted-by":"publisher","first-page":"52","DOI":"10.2307\/2319261","volume":"80","author":"P. Erd\u00f6s","year":"1973","unstructured":"Erd\u00f6s, P., Guy, R.P.: Crossing number problems. American Mathematical Monthly\u00a080, 52\u201358 (1973)","journal-title":"American Mathematical Monthly"},{"key":"36_CR5","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/BF01187020","volume":"11","author":"P. Eades","year":"1994","unstructured":"Eades, P., Wormald, N.: Edge crossings in drawings of bipartite graphs. Algorithmica\u00a011, 379\u2013403 (1994)","journal-title":"Algorithmica"},{"key":"36_CR6","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1137\/0604033","volume":"4","author":"M.R. Garey","year":"1983","unstructured":"Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods\u00a04, 312\u2013316 (1983)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"36_CR7","doi-asserted-by":"publisher","first-page":"146","DOI":"10.2307\/2689132","volume":"42","author":"F. Harary","year":"1969","unstructured":"Harary, F.: Determinants, permanents and bipartite graphs. Mathematical Magazine\u00a042, 146\u2013148 (1969)","journal-title":"Mathematical Magazine"},{"key":"36_CR8","first-page":"203","volume":"1","author":"F. Harary","year":"1972","unstructured":"Harary, F., Schwenk, A.: A new crossing number for bipartite graphs. Utilitas Mathematica\u00a01, 203\u2013209 (1972)","journal-title":"Utilitas Mathematica"},{"key":"36_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00001","volume":"1","author":"M. J\u00fcnger","year":"1997","unstructured":"J\u00fcnger, M., Mutzel, P.: 2-layer straight line crossing minimization: performance of exact and heuristic algorithms. Journal of Graph Algorithms and Applications\u00a01, 1\u201325 (1997)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"36_CR10","volume-title":"Complexity Issues in VLSI","author":"F.T. Leighton","year":"1983","unstructured":"Leighton, F.T.: Complexity Issues in VLSI. MIT Press, Cambridge (1983)"},{"key":"36_CR11","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1016\/S0377-2217(97)00291-9","volume":"106","author":"R. Mart\u00ed","year":"1998","unstructured":"Mart\u00ed, R.: A tabu search algorithm for the bipartite drawing problem. European Journal of Operational Research\u00a0106, 558\u2013569 (1998)","journal-title":"European Journal of Operational Research"},{"key":"36_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/3-540-46648-7_22","volume-title":"Graph Drawing","author":"C. Matuszewski","year":"1999","unstructured":"Matuszewski, C., Sch\u00f6nfeld, R., Molitor, P.: Using sifting for k-layer crossing minimization. In: Kratochv\u00edl, J. (ed.) GD 1999. LNCS, vol.\u00a01731, pp. 217\u2013224. Springer, Heidelberg (1999)"},{"key":"36_CR13","first-page":"85","volume":"17","author":"M. May","year":"1988","unstructured":"May, M., Szkatula, K.: On the bipartite crossing number. Control and Cybernetics\u00a017, 85\u201398 (1988)","journal-title":"Control and Cybernetics"},{"key":"36_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/3-540-36151-0_29","volume-title":"Graph Drawing","author":"M. Newton","year":"2002","unstructured":"Newton, M., S\u00fdkora, O., Vrt\u2019o, I.: Two new heuristics for two-sided bipartite graph drawings. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol.\u00a02528, pp. 312\u2013319. Springer, Heidelberg (2002)"},{"key":"36_CR15","doi-asserted-by":"crossref","DOI":"10.1002\/9781118033203","volume-title":"Combinatorial Geometry","author":"J. Pach","year":"1995","unstructured":"Pach, J., Agarwal, P.K.: Combinatorial Geometry. Wiley and Sons, New York (1995)"},{"key":"36_CR16","unstructured":"Odenthal, T.: Personal communication (2002)"},{"key":"36_CR17","volume-title":"An Introduction to VLSI Physical Design","author":"M. Sarrafzadeh","year":"1995","unstructured":"Sarrafzadeh, M.: An Introduction to VLSI Physical Design. McGraw-Hill, New York (1995)"},{"key":"36_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/3-540-63307-3_48","volume-title":"Algorithms and Data Structures","author":"F. Shahrokhi","year":"1997","unstructured":"Shahrokhi, F., S\u00fdkora, O., Sz\u00e9kely, L.A., Vrt\u2019o, I.: On the bipartite drawings and the linear arrangement problem. In: Rau-Chaplin, A., Dehne, F., Sack, J.-R., Tamassia, R. (eds.) WADS 1997. LNCS, vol.\u00a01272, pp. 55\u201368. Springer, Heidelberg (1997)"},{"key":"36_CR19","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/S0304-3975(99)00285-6","volume":"245","author":"F. Shahrokhi","year":"2000","unstructured":"Shahrokhi, F., S\u00fdkora, O., Sz\u00e9kely, L.A., Vrt\u2019o, I.: A new lower bound for the bipartite crossing number with applications. Theoretical Computer Science\u00a0245, 281\u2013294 (2000)","journal-title":"Theoretical Computer Science"},{"key":"36_CR20","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/S0166-218X(87)80003-3","volume":"19","author":"J. Spinrad","year":"1987","unstructured":"Spinrad, J., Brandst\u00e4dt, A., Stewart, L.: Bipartite permutation graphs. Discrete Applied Mathematics\u00a019, 279\u2013292 (1987)","journal-title":"Discrete Applied Mathematics"},{"key":"36_CR21","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1109\/TSMC.1981.4308636","volume":"11","author":"K. Sugiyama","year":"1981","unstructured":"Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical systems structures. IEEE Transactions on Systems, Man and Cybernetics\u00a011, 109\u2013125 (1981)","journal-title":"Man and Cybernetics"},{"key":"36_CR22","first-page":"502","volume":"7","author":"J. Warfield","year":"1977","unstructured":"Warfield, J.: Crossing theory and hierarchy mapping. IEEE Transactions on Systems. Man and Cybernetics\u00a07, 502\u2013523 (1977)","journal-title":"Man and Cybernetics"},{"key":"36_CR23","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1111\/j.1749-6632.1970.tb56499.x","volume":"175","author":"M.E. Watkins","year":"1970","unstructured":"Watkins, M.E.: A special crossing number for bipartite graphs: a research problem. Annals of New York Academy Sciences\u00a0175, 405\u2013410 (1970)","journal-title":"Annals of New York Academy Sciences"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-31843-9_36.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:28:18Z","timestamp":1605742098000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-31843-9_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540245285","9783540318439"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-31843-9_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}