{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T15:03:48Z","timestamp":1748358228668},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2010,6,17]],"date-time":"2010-06-17T00:00:00Z","timestamp":1276732800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2010,9]]},"DOI":"10.1007\/s00454-010-9245-4","type":"journal-article","created":{"date-parts":[[2010,6,16]],"date-time":"2010-06-16T20:33:29Z","timestamp":1276720409000},"page":"463-483","source":"Crossref","is-referenced-by-count":4,"title":["General Lower Bounds for the Minor Crossing Number of Graphs"],"prefix":"10.1007","volume":"44","author":[{"given":"Drago","family":"Bokal","sequence":"first","affiliation":[]},{"given":"\u00c9va","family":"Czabarka","sequence":"additional","affiliation":[]},{"given":"L\u00e1szl\u00f3 A.","family":"Sz\u00e9kely","sequence":"additional","affiliation":[]},{"given":"Imrich","family":"Vrt\u2019o","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,6,17]]},"reference":[{"key":"9245_CR1","volume-title":"Proofs from the Book","author":"M. Aigner","year":"2000","unstructured":"Aigner, M., Ziegler, G.M.: Proofs from the Book. Springer, Berlin (2000)"},{"key":"9245_CR2","series-title":"Ann. Discrete Math.","first-page":"9","volume-title":"Theory and Practice of Combinatorics: A Collection of Articles Honoring Anton Kotzig on the Occasion of His Sixtieth Birthday","author":"M. Ajtai","year":"1983","unstructured":"Ajtai, M., Chv\u00e1tal, V., Newborn, M.M., Szemer\u00e9di, E.: Crossing-free subgraphs. In: Rosa, A., Sabidussi, G., Turgeon, J. (eds.) Theory and Practice of Combinatorics: A Collection of Articles Honoring Anton Kotzig on the Occasion of His Sixtieth Birthday. Ann. Discrete Math., vol. 12, pp.\u00a09\u201312. North-Holland, Amsterdam (1983)"},{"key":"9245_CR3","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1137\/S0895480194272183","volume":"9","author":"L. Alexandrov","year":"1996","unstructured":"Alexandrov, L., Djidjev, H.: Linear algorithms for partitioning embedded graphs of bounded genus. SIAM J. Discrete Math. 9, 129\u2013150 (1996)","journal-title":"SIAM J. Discrete Math."},{"key":"9245_CR4","doi-asserted-by":"crossref","first-page":"1607","DOI":"10.1073\/pnas.45.11.1607","volume":"45","author":"S. Benzer","year":"1959","unstructured":"Benzer, S.: On the topology of the genetic fine structure. Proc. Natl. Akad. Sci. USA 45, 1607\u20131620 (1959)","journal-title":"Proc. Natl. Akad. Sci. USA"},{"key":"9245_CR5","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1002\/jgt.20258","volume":"56","author":"D. Bokal","year":"2007","unstructured":"Bokal, D.: On the crossing number of Cartesian products with trees. J. Graph Theory 56, 287\u2013300 (2007)","journal-title":"J. Graph Theory"},{"key":"9245_CR6","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1137\/05062706X","volume":"20","author":"D. Bokal","year":"2006","unstructured":"Bokal, D., Fijav\u017e, G., Mohar, B.: The minor crossing number. SIAM J. Discrete Math. 20, 344\u2013356 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"9245_CR7","volume":"15","author":"D. Bokal","year":"2008","unstructured":"Bokal, D., Fijav\u017e, G., Wood, D.R.: The minor crossing number of graphs with an excluded minor. Electron. J. Comb. 15, R4 (2008). http:\/\/www.combinatorics.org\/Volume_15\/Abstracts\/v15i1r4.html","journal-title":"Electron. J. Comb."},{"key":"9245_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0166-218X(96)00076-5","volume":"75","author":"B. Bollob\u00e1s","year":"1997","unstructured":"Bollob\u00e1s, B., Leader, I.: Matchings and paths in the cube. Discrete Appl. Math. 75, 1\u20138 (1997)","journal-title":"Discrete Appl. Math."},{"key":"9245_CR9","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1080\/00029890.1973.11993230","volume":"80","author":"P. Erd\u0151s","year":"1973","unstructured":"Erd\u0151s, P., Guy, R.K.: Crossing number problems. Am. Math. Mon. 80, 52\u201358 (1973)","journal-title":"Am. Math. Mon."},{"key":"9245_CR10","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1002\/1097-0118(200103)36:3<168::AID-JGT1004>3.0.CO;2-#","volume":"36","author":"E. Garcia-Moreno","year":"2001","unstructured":"Garcia-Moreno, E., Salazar, G.: Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree. J. Graph Theory 36, 168\u2013173 (2001)","journal-title":"J. Graph Theory"},{"key":"9245_CR11","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1016\/0196-6774(84)90019-1","volume":"5","author":"J.R. Gilbert","year":"1984","unstructured":"Gilbert, J.R., Hutchinson, J.P., Tarjan, R.E.: A separator theorem for graphs of bounded genus. J.\u00a0Algorithms 5, 391\u2013407 (1984)","journal-title":"J.\u00a0Algorithms"},{"key":"9245_CR12","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1007\/s00493-006-0026-x","volume":"26","author":"C. Houdr\u00e9","year":"2006","unstructured":"Houdr\u00e9, C., Stoyanov, T.: Expansion and isoperimetric constants for product graphs. Combinatorica 26, 455\u2013473 (2006)","journal-title":"Combinatorica"},{"key":"9245_CR13","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/S0095-8956(03)00026-1","volume":"88","author":"H.A. Juarez","year":"2003","unstructured":"Juarez, H.A., Salazar, G.: Optimal meshes of curves in the Klein bottle. J. Comb. Theory Ser. B 88, 185\u2013188 (2003)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9245_CR14","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0095-8956(91)90090-7","volume":"52","author":"J. Kratochv\u00edl","year":"1991","unstructured":"Kratochv\u00edl, J.: String graphs I: the number of critical nonstring graphs is infinite. J. Comb. Theory Ser. B 52, 53\u201366 (1991)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9245_CR15","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0095-8956(91)90091-W","volume":"52","author":"J. Kratochv\u00edl","year":"1991","unstructured":"Kratochv\u00edl, J.: String graphs II: recognizing string graphs is NP-hard. J. Comb. Theory Ser. B 52, 67\u201378 (1991)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9245_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0095-8956(91)90050-T","volume":"53","author":"J. Kratochv\u00edl","year":"1991","unstructured":"Kratochv\u00edl, J., Matou\u0161ek, J.: String graphs requiring exponential representations. J. Comb. Theory Ser. B 53, 1\u20134 (1991)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9245_CR17","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":"9245_CR18","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36, 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"key":"9245_CR19","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"B. Mohar","year":"2001","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins University Press, Baltimore (2001)"},{"key":"9245_CR20","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1007\/s00454-002-2891-4","volume":"28","author":"J. Pach","year":"2002","unstructured":"Pach, J., T\u00f3th, G.: Recognizing string graphs is decidable. Discrete Comput. Geom. 28, 593\u2013606 (2002)","journal-title":"Discrete Comput. Geom."},{"key":"9245_CR21","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1002\/(SICI)1097-0118(199607)22:3<239::AID-JGT4>3.0.CO;2-N","volume":"22","author":"J. Pach","year":"1996","unstructured":"Pach, J., Shahrokhi, F., Szegedy, M.: Applications of crossing number. J. Graph Theory 22, 239\u2013243 (1996)","journal-title":"J. Graph Theory"},{"key":"9245_CR22","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1007\/s004540010011","volume":"28","author":"J. Pach","year":"2000","unstructured":"Pach, J., Spencer, J., T\u00f3th, G.: New bounds on crossing numbers. Discrete Comput. Geom. 28, 623\u2013644 (2000)","journal-title":"Discrete Comput. Geom."},{"key":"9245_CR23","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1145\/997817.997831","volume-title":"Proceedings of the Twentieth Annual Symposium on Computational Geometry","author":"J. Pach","year":"2004","unstructured":"Pach, J., Radoi\u010di\u0107, R., Tardos, G., T\u00f3th, G.: Improving the crossing lemma by finding more crossings in sparse graphs. In: Snoeyink, J., Boissonnat, J.D. (eds.) Proceedings of the Twentieth Annual Symposium on Computational Geometry, pp. 68\u201375. ACM, New York (2004)"},{"key":"9245_CR24","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/BF02574034","volume":"13","author":"R.B. Richter","year":"1995","unstructured":"Richter, R.B., Thomassen, C.: Intersections of curve systems and the crossing number of C 5\u00d7C 5. Discrete Comput. Geom. 13, 149\u2013159 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"9245_CR25","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/j.jcss.2003.07.002","volume":"68","author":"M. Schaefer","year":"2004","unstructured":"Schaefer, M., \u0160tefankovi\u010d, D.: Decidability of string graphs. J. Comput. Syst. Sci. 68, 319\u2013334 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"9245_CR26","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/S0022-0000(03)00045-X","volume":"67","author":"M. Schaefer","year":"2003","unstructured":"Schaefer, M., Sedgwick, E., \u0160tefankovi\u010d, D.: String graphs in NP. J. Comput. Syst. Sci. 67, 365\u2013380 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"9245_CR27","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1006\/aima.1996.0069","volume":"123","author":"F. Shahrokhi","year":"1996","unstructured":"Shahrokhi, F., S\u00fdkora, O., Sz\u00e9kely, L.A., Vr\u0165o, I.: The crossing number of a graph on a compact 2-manifold. Adv. Math. 123, 105\u2013119 (1996)","journal-title":"Adv. Math."},{"key":"9245_CR28","doi-asserted-by":"crossref","first-page":"1639","DOI":"10.1002\/j.1538-7305.1966.tb01713.x","volume":"45","author":"F.W. Sinden","year":"1966","unstructured":"Sinden, F.W.: Topology of thin film RC circuits. Bell Syst. Tech. J. 45, 1639\u20131662 (1966)","journal-title":"Bell Syst. Tech. J."},{"key":"9245_CR29","unstructured":"Smith, W.D., Wormald, N.C.: Geometric separator theorems and applications. Manuscript (1998), 50\u00a0pp. http:\/\/www.math.uwaterloo.ca\/~nwormald\/papers\/geomsep.ps.gz (2007)"},{"key":"9245_CR30","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., Vr\u0165o, I.: Edge separators for graphs of bounded genus with applications. Theor. Comput. Sci. 112, 419\u2013429 (1993)","journal-title":"Theor. Comput. Sci."},{"key":"9245_CR31","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1017\/S0963548397002976","volume":"6","author":"L.A. Sz\u00e9kely","year":"1997","unstructured":"Sz\u00e9kely, L.A.: Crossing numbers and hard Erd\u0151s problems in discrete geometry. Comb. Probab. Comput. 6, 353\u2013358 (1997)","journal-title":"Comb. Probab. Comput."},{"key":"9245_CR32","unstructured":"Wada, K., Kawaguchi, K.: Optimal bounds of the crossing number and bisection width for generalized hypercube graphs. In: Proc. 16th Biennial Symposium on Communications, pp. 323\u2013326 (1992)"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-010-9245-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-010-9245-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-010-9245-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,27]],"date-time":"2024-03-27T17:06:06Z","timestamp":1711559166000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-010-9245-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,17]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["9245"],"URL":"https:\/\/doi.org\/10.1007\/s00454-010-9245-4","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,6,17]]}}}