{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T10:42:13Z","timestamp":1756464133065},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540633075"},{"type":"electronic","value":"9783540694229"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63307-3_48","type":"book-chapter","created":{"date-parts":[[2010,4,5]],"date-time":"2010-04-05T19:22:48Z","timestamp":1270495368000},"page":"55-68","source":"Crossref","is-referenced-by-count":7,"title":["On bipartite crossings, largest biplanar subgraphs, and the linear arrangement problem"],"prefix":"10.1007","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":"297","published-online":{"date-parts":[[2005,7,30]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0898-1221(84)90085-3","volume":"10","author":"F. R. K. Chung","year":"1984","unstructured":"Chung, F. R. K., On optimal linear arrangements of trees, Computers and Mathematics with Applications 10, (1984), 43\u201360.","journal-title":"Computers and Mathematics with Applications"},{"key":"6_CR2","doi-asserted-by":"crossref","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 20 (1978), 601\u2013604.","journal-title":"SIAM Review"},{"key":"6_CR3","series-title":"Lecture Notes in Computer Scince","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/3-540-55808-X_2","volume-title":"Proc. International Symposium on Mathematical Foundations of Computer Sciences","author":"J. D\u00edaz","year":"1992","unstructured":"D\u00edaz, J., Graph layout problems, in: Proc. International Symposium on Mathematical Foundations of Computer Sciences, Lecture Notes in Computer Scince 629, Springer Verlag, Berlin, 1992, 14\u201321."},{"key":"6_CR4","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0925-7721(94)00014-X","volume":"4","author":"J. Battista Di","year":"1994","unstructured":"Di Battista, J., Eades, P., Tamassia, R., Tollis, I. G., Algorithms for drawing graphs: an annotated bibliography, Computational Geometry 4 (1994), 235\u2013282.","journal-title":"Computational Geometry"},{"key":"6_CR5","doi-asserted-by":"crossref","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 11 (1994), 379\u2013403.","journal-title":"Algorithmica"},{"key":"6_CR6","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/0304-3975(94)90179-1","volume":"131","author":"P. Eades","year":"1994","unstructured":"Eades, P., Whitesides, S., Drawing graphs in 2 layers, Theoretical Computer Sceince 131, 1994, 361\u2013374.","journal-title":"Theoretical Computer Sceince"},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"Even, G., Naor, J. S., Rao, S., Scieber, B., Divide-and-Conquer approximation algorithms via spreading metrices, in Proc. 36th Annual IEEE Symposium on Foundation of Computer Science, IEEE Computer Society Press, 1995, 62\u201371.","DOI":"10.1109\/SFCS.1995.492463"},{"key":"6_CR8","unstructured":"Even, G., Naor, J. S., Rao, S., Scieber, B., Fast Approximate Graph Partition Algorithms, 8th Annual ACM-SIAM Symposium on Disc. Algo., 1997, 639\u2013648."},{"key":"6_CR9","doi-asserted-by":"crossref","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 J. Algebraic and Discrete Methods 4 (1983), 312\u2013316.","journal-title":"SIAM J. Algebraic and Discrete Methods"},{"key":"6_CR10","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1080\/0025570X.1969.11975950","volume":"42","author":"F. Harary","year":"1969","unstructured":"Harary, F., Determinants, permanents and bipartite graphs, Mathematical Magazine 42 (1969), 146\u2013148.","journal-title":"Mathematical Magazine"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Hansen, M., Approximate algorithms for geometric embeddings in the plane with applications to parallel processing problems, 30th FOGS, 1989, 604\u2013609.","DOI":"10.1109\/SFCS.1989.63542"},{"key":"6_CR12","first-page":"203","volume":"1","author":"F. Harary","year":"1972","unstructured":"Harary, F., Schwenk, A., A new crossing number for bipartite graphs, Utilitas Mathematica 1 (1972), 203\u2013209.","journal-title":"Utilitas Mathematica"},{"key":"6_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/BFb0021817","volume-title":"Proc. Graph Drawing'95","author":"M. J\u00fcnger","year":"1996","unstructured":"J\u00fcnger, M., Mutzel, P., Exact and heuristic algorithm for 2-layer straightline crossing number, in: Proc. Graph Drawing'95, Lecture Notes in Computer Science 1027, Springer Verlag, Berlin, 1996, 337\u2013348."},{"key":"6_CR14","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0166-218X(92)90229-4","volume":"36","author":"M. Juvan","year":"1992","unstructured":"Juvan, M., Mohar, B., Optimal linear labelings and eigenvalues of graphs, Discrete Mathematics 36 (1992), 153\u2013168.","journal-title":"Discrete Mathematics"},{"key":"6_CR15","unstructured":"Leighton, F.T., Complexity issues in VLSI, MIT Press, 1983."},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Leighton F. T., Rao, S., An approximate max flow min cut theorem for multicommodity flow problem with applications to approximation algorithm, 29th Foundation of Computer Science, IEEE Computer Society Press, 1988, 422\u2013431.","DOI":"10.1109\/SFCS.1988.21958"},{"key":"6_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-92106-2","volume-title":"Combinatorial algorithms for integrated circuit layouts","author":"T. Lengauer","year":"1990","unstructured":"Lengauer, T., Combinatorial algorithms for integrated circuit layouts, Wiley and Sons, Chichester, UK, 1990."},{"key":"6_CR18","first-page":"85","volume":"17","author":"M. May","year":"1988","unstructured":"May, M., Szkatula, K., On the bipartite crossing number, Control and Cybernetics 17 (1988), 85\u201398.","journal-title":"Control and Cybernetics"},{"key":"6_CR19","series-title":"Lecture Notes in Computer Science","volume-title":"Proceeding of Graph Drawing 96","author":"P. Mutzel","year":"1997","unstructured":"Mutzel, P., An alrenative method to crossing minimization on hierarchical graphs, Proceeding of Graph Drawing 96, Lecture Notes in Computer Science, Springer Verlag, Berin, 1997."},{"key":"6_CR20","first-page":"56","volume":"19","author":"M. A. Seidvasser","year":"1970","unstructured":"Seidvasser, M. A., The optimal number of the vertices of a tree, Diskretnii Analiz 19 (1970), 56\u201374.","journal-title":"Diskretnii Analiz"},{"key":"6_CR21","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1137\/0208002","volume":"8","author":"Y. Shiloach","year":"1979","unstructured":"Shiloach, Y., A minimum linear arrangement algorithm for undirected trees, SIAM J. Computing 8 (1979), 15\u201332.","journal-title":"SIAM J. Computing"},{"key":"6_CR22","doi-asserted-by":"crossref","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 19, 1987, 279\u2013292.","journal-title":"Discrete Applied Mathematics"},{"key":"6_CR23","doi-asserted-by":"crossref","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 11 (1981), 109\u2013125.","journal-title":"IEEE Transactions on Systems, Man and Cybernetics"},{"key":"6_CR24","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 7 (1977), 502\u2013523.","journal-title":"IEEE Transactions on Systems, Man and Cybernetics"},{"key":"6_CR25","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 175 (1970), 405\u2013410.","journal-title":"Annals of New York Academy Sciences"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63307-3_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,3]],"date-time":"2020-06-03T14:04:11Z","timestamp":1591193051000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63307-3_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540633075","9783540694229"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-63307-3_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}