{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:08:01Z","timestamp":1725664081137},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540589501"},{"type":"electronic","value":"9783540491552"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-58950-3_364","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:54:03Z","timestamp":1330275243000},"page":"131-142","source":"Crossref","is-referenced-by-count":9,"title":["Crossing numbers of graphs, lower bound techniques and algorithms: A survey"],"prefix":"10.1007","author":[{"given":"Farhad","family":"Shahrokhi","sequence":"first","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,6,1]]},"reference":[{"key":"14_CR1","first-page":"9","volume":"12","author":"M. Ajtai","year":"1982","unstructured":"Ajtai, M., Chv\u00e1tal, V., Newborn, M., M. Szemer\u00e9dy, E., \u201cCrossing-free subgraphs\u201d, Annals of Discrete Mathematics\n12 (1982), 9\u201312.","journal-title":"Annals of Discrete Mathematics"},{"key":"14_CR2","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"Alon, N., Spencer, J.H., Erd\u00f6s, P., \u201cThe Probabilistic Method\u201d, Wiley and Sons, New York, 1992."},{"key":"14_CR3","first-page":"9","volume-title":"A graphtheoretic approach to aesthetic layout of information systems diagrams","author":"C. Batini","year":"1984","unstructured":"Batini, C., Nardelli, E., Talamo, M., Tamassia, R., A graphtheoretic approach to aesthetic layout of information systems diagrams, in: Proc. 10th Intl. Workshop on Graph-Theoretic Concepts in Computer Science, Trauner Verlag, Berlin, 1984, 9\u201318."},{"key":"14_CR4","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1002\/jgt.3190040203","volume":"4","author":"L. W. Beineke","year":"1980","unstructured":"Beineke, L. W., Ringeisen, R. D., On the crossing number product of cycles and graphs of order four, J. Graph Theory\n4(1980), 145\u2013155.","journal-title":"J. Graph Theory"},{"key":"14_CR5","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1002\/jgt.3190160502","volume":"16","author":"D. Bienstock","year":"1992","unstructured":"Bienstock, D., Dean, N., \u201cNew results on rectilinear crossing Numbers and Plane Embeddings\u201d, J. Graph Theory, 16 (1992), 389\u2013398.","journal-title":"J. Graph Theory"},{"key":"14_CR6","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1002\/jgt.3190170308","volume":"17","author":"D. Bienstock","year":"1993","unstructured":"Bienstock, D., Dean, N., \u201cBounds on the rectilinear crossing Numbers\u201d, J. Graph Theory\n17 (1993), 333\u2013348.","journal-title":"J. Graph Theory"},{"key":"14_CR7","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","volume":"28","author":"S. N. Bhatt","year":"1984","unstructured":"Bhatt, S. N., Leighton, F. T., \u201cA framework for Solving VLSI Graph Layout Problems\u201d, Journal of Computer and System Sciences\n28 (1984), 300\u2013343.","journal-title":"Journal of Computer and System Sciences"},{"key":"14_CR8","first-page":"1","volume-title":"A near optimal algorithm for edge separators","author":"F. R. K. Chung","year":"1994","unstructured":"Chung, F. R. K., Yau, S.T., \u201cA near optimal algorithm for edge separators\u201d, in: Proc. 26th Annual ACM Symposium on the Theory on Computing, ACM, New York, 1994, 1\u20138."},{"key":"14_CR9","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1080\/00029890.1973.11993230","volume":"80","author":"P. Erd\u00f6s","year":"1973","unstructured":"Erd\u00f6s, P., Guy, R. P., Crossing number problems, American Mathematical Monthly\n80(1973), 52\u201358.","journal-title":"American Mathematical Monthly"},{"key":"14_CR10","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/BF01187020","volume":"11","author":"P. Eades","year":"1994","unstructured":"Eades, P., Wormald, N. C., Edge crossings in drawings of bipartite graphs, Algorithmica(1994), 11, 379\u2013403.","journal-title":"Algorithmica"},{"key":"14_CR11","first-page":"229","volume":"11","author":"I. F\u00e1ry","year":"1948","unstructured":"F\u00e1ry, I., \u201cOn Straight Line Representations of Graphs\u201d, Acta. Univ. Szeged Sect. Sci. Math., 11, 1948, 229\u2013233.","journal-title":"Acta. Univ. Szeged Sect. Sci. Math."},{"key":"14_CR12","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. Alg. Discrete Methods\n4(1983), 312\u2013316.","journal-title":"SIAM J. Alg. Discrete Methods"},{"key":"14_CR13","series-title":"Lecture Notes in Computer Science 450","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1007\/3-540-52921-7_83","volume-title":"Proc. Algorithms, Intl. Symp. SIGAL'90","author":"H. Gazit","year":"1990","unstructured":"Gazit, H., Miller, G.L., Planar separators and the Euclidean norm, in: Proc. Algorithms, Intl. Symp. SIGAL'90, Lecture Notes in Computer Science 450, Springer Verlag, Berlin, 1990, 338\u2013347."},{"key":"14_CR14","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1002\/jgt.3190020211","volume":"2","author":"J. L. Gross","year":"1978","unstructured":"Gross, J. L., On infinite family of octahedral crossing numbers, J. Graph Theory\n2 (1978), 171\u2013178.","journal-title":"J. Graph Theory"},{"key":"14_CR15","first-page":"68","volume":"7","author":"R.K. Guy","year":"1960","unstructured":"Guy, R.K., A combinatorial problem, Nabla (Bull. Malayan Math. Soc.)\n7 (1960), 68\u201372.","journal-title":"Nabla (Bull. Malayan Math. Soc.)"},{"key":"14_CR16","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1016\/S0021-9800(68)80063-8","volume":"4","author":"R. K. Guy","year":"1968","unstructured":"Guy, R. K., Jenkins, T., Schaer, J., The toroidal crossing number of the complete graph, J. Combinatorial Theory\n4 (1968), 376\u2013390.","journal-title":"J. Combinatorial Theory"},{"key":"14_CR17","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/S0021-9800(69)80084-0","volume":"6","author":"R. K. Guy","year":"1969","unstructured":"Guy, R. K., Jenkins, T., The toroidal crossing number of K\nm, n, J. Combinatorial Theory\n6 (1969), 235\u2013250.","journal-title":"J. Combinatorial Theory"},{"key":"14_CR18","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0095-8956(72)90042-1","volume":"12","author":"P. C. Kainen","year":"1972","unstructured":"Kainen, P. C., A lower bound for crossing number of graphs with applications to K\nn, Kp,q and Q(d), J. Combinatorial Theory (B) 12 (1972), 287\u2013298.","journal-title":"J. Combinatorial Theory (B)"},{"key":"14_CR19","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1002\/jgt.3190020302","volume":"2","author":"P. C. Kainen","year":"1978","unstructured":"Kainen, P. C., White, A. T., On stable crossing numbers, J. Graph Theory\n2 (1978) 181\u2013187.","journal-title":"J. Graph Theory"},{"key":"14_CR20","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/S0021-9800(70)80087-4","volume":"9","author":"D. J. Kleitman","year":"1970","unstructured":"Kleitman, D. J., The crossing number of K\n5,n, J. Combinatorial Theory\n9 (1970), 315\u2013323.","journal-title":"J. Combinatorial Theory"},{"key":"14_CR21","volume-title":"Complexity Issues in VLSI","author":"F. T. Leighton","year":"1983","unstructured":"Leighton, F. T., Complexity Issues in VLSI, MIT Press, Cambridge, 1983. Malitz, S.M., \u201cGenus g Graphs have Pagenumber O(\u221ag)\u201d, Journal of Algorithms, 17 (1), 84\u2013109, 1994."},{"key":"14_CR22","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1002\/jgt.3190150109","volume":"15","author":"T. Madej","year":"1991","unstructured":"Madej, T., Bounds for the crossing number of the n-cube, J. Graph Theory\n15 (1991), 81\u201397.","journal-title":"J. Graph Theory"},{"key":"14_CR23","first-page":"339","volume":"30","author":"G. Pica","year":"1986","unstructured":"Pica, G., Pisanski., T., Ventre, A.G.S., \u201cCartesian product of graphs and their crossing numbers, Annals of Discrete Mathematics\n30(1986), 339\u2013346.","journal-title":"Annals of Discrete Mathematics"},{"key":"14_CR24","volume-title":"Applications of crossing numbers","author":"J. Pach","year":"1994","unstructured":"Pach, J., Shahrokhi, F., Szegedy, M., Applications of crossing numbers, in: Proc. 10th Annual ACM Symposium on Computational Geometry, ACM, New York, 1994."},{"key":"14_CR25","unstructured":"Shahrokhi, F., S\u00fdkora, O., Sz\u00e9kely, L. A., Vrt'o, I., The crossing number of a graph on a compact 2-manifold, Advances in Mathematics, to appear."},{"key":"14_CR26","unstructured":"Shahrokhi, F., Sz\u00e9kely, L. A., \u201cEffective lower bounds for crossing number, bisection width and balanced vertex separators in terms of symmetry\u201d, in: Proc. 2nd IPCO Conf., Pittsburgh, 1992, 102\u2013113, also to appear in Combinatorics, Probability and Computing."},{"key":"14_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1007\/3-540-57899-4_68","volume-title":"Improved bounds for the crossing numbers on surfaces of genus g","author":"F. Shahrokhi","year":"1994","unstructured":"Shahrokhi, F., S\u00fdkora, O., Sz\u00e9kely, L. A., Vrt'o, I., \u201cImproved bounds for the crossing numbers on surfaces of genus g\u201d, in: Proc. 19-th Intl. Workshop on Graph-Theoretic Concepts in Computer Science WG'93, Lecture Notes in Computer Science, Springer Verlag, Berlin, 1994, 388\u2013395, to appear in Algorithmica."},{"key":"14_CR28","series-title":"Lecture Notes in Computer Science","volume-title":"On Book Embeddings and Crossing Numbers","author":"F. Shahrokhi","year":"1995","unstructured":"Shahrokhi, F., S\u00fdkora, O., Sz\u00e9kely, L. A., Vrt'o, I., \u201cOn Book Embeddings and Crossing Numbers\u201d, to appear in Proc. 20-th Intl. Workshop on Graph-Theoretic Concepts in Computer Science WG'94, Lecture Notes in Computer Science, Springer Verlag, Berlin, 1995."},{"key":"14_CR29","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1016\/0304-3975(93)90031-N","volume":"112","author":"O. S\u00fdkora","year":"1993","unstructured":"S\u00fdkora, O., Vrto, I., Edge separators for graphs of bounded genus with applications, Theoretical Computer Science\n112 (1993), 419\u2013429.","journal-title":"Theoretical Computer Science"},{"key":"14_CR30","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0167-9260(94)90021-3","volume":"17","author":"O. S\u00fdkora","year":"1994","unstructured":"S\u00fdkora, O., Vrt'o, I., On VLSI layout of the star graph and related networks, Integration, the VLSI Journal\n17 (1994), 83\u201393.","journal-title":"Integration, the VLSI Journal"},{"key":"14_CR31","unstructured":"White, A. T., Beineke, L. W., Topological graph theory, in: Selected Topics in Graph Theory, eds. L. W. Beineke and R. J. Wilson, Academic Press, 1978, 15\u201350."}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58950-3_364.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:21:25Z","timestamp":1619572885000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58950-3_364"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540589501","9783540491552"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/3-540-58950-3_364","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}