{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T18:13:38Z","timestamp":1758824018088},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,5,11]],"date-time":"2012-05-11T00:00:00Z","timestamp":1336694400000},"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":[[2012,9]]},"DOI":"10.1007\/s00454-012-9430-8","type":"journal-article","created":{"date-parts":[[2012,5,10]],"date-time":"2012-05-10T14:14:53Z","timestamp":1336659293000},"page":"393-415","source":"Crossref","is-referenced-by-count":2,"title":["Planar Crossing Numbers of Graphs of Bounded Genus"],"prefix":"10.1007","volume":"48","author":[{"given":"Hristo N.","family":"Djidjev","sequence":"first","affiliation":[]},{"given":"Imrich","family":"Vrt\u2019o","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,5,11]]},"reference":[{"key":"9430_CR1","first-page":"9","volume":"12","author":"M. Ajtai","year":"1982","unstructured":"Ajtai, M., Chv\u00e1tal, V., Newborn, M.M., Szemer\u00e9di, E.: Crossing-free subgraphs. Ann. Discrete Math. 12, 9\u201312 (1982)","journal-title":"Ann. Discrete Math."},{"issue":"5","key":"9430_CR2","doi-asserted-by":"crossref","first-page":"1005","DOI":"10.1142\/S0129054106004236","volume":"17","author":"K.J. B\u00f6r\u00f6zky","year":"2006","unstructured":"B\u00f6r\u00f6zky, K.J., Pach, J., T\u00f3th, G.: Planar crossing numbers of graphs embeddable in another surface. Int. J. Found. Comput. Sci. 17(5), 1005\u20131016 (2006)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9430_CR3","first-page":"284","volume-title":"Proceedings of the 16th Annual European Symposium on Algorithms, ESA\u201908","author":"M. Chimani","year":"2008","unstructured":"Chimani, M., Mutzel, P., Bomze, I.: A new approach to exact crossing minimization. In: Proceedings of the 16th Annual European Symposium on Algorithms, ESA\u201908, pp. 284\u2013296. Springer, Berlin (2008)"},{"key":"9430_CR4","first-page":"303","volume-title":"STOC","author":"J. Chuzhoy","year":"2011","unstructured":"Chuzhoy, J.: An algorithm for the graph crossing number problem. In: Fortnow, L., Vadhan, S.P. (eds.) STOC, pp. 303\u2013312. ACM, New York (2011)"},{"key":"9430_CR5","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/S0166-218X(01)00314-6","volume":"122","author":"R. Cimikowski","year":"2002","unstructured":"Cimikowski, R.: Algorithms for the fixed linear crossing number problem. Discrete Appl. Math. 122, 93\u2013115 (2002)","journal-title":"Discrete Appl. Math."},{"key":"9430_CR6","volume-title":"Graph Drawing: Algorithms for Visualization of Graphs","author":"G. Di\u00a0Battista","year":"1999","unstructured":"Di\u00a0Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for Visualization of Graphs. Prentice Hall, New York (1999)"},{"issue":"3","key":"9430_CR7","doi-asserted-by":"crossref","first-page":"245","DOI":"10.7155\/jgaa.00069","volume":"7","author":"H. Djidjev","year":"2003","unstructured":"Djidjev, H., Vrto, I.: Crossing numbers and cutwidths. J. Graph Algorithms Appl. 7(3), 245\u2013251 (2003)","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"9430_CR8","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/s004530010031","volume":"28","author":"H.N. Djidjev","year":"2000","unstructured":"Djidjev, H.N.: Partitioning planar graphs with vertex costs: algorithms and applications. Algorithmica 28(1), 51\u201375 (2000)","journal-title":"Algorithmica"},{"issue":"1","key":"9430_CR9","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1137\/S0097539700373520","volume":"32","author":"G. Even","year":"2002","unstructured":"Even, G., Guha, S., Schieber, B.: Improved approximations of crossings in graph drawings and VLSI layout areas. SIAM J. Comput. 32(1), 231\u2013252 (2002)","journal-title":"SIAM J. Comput."},{"key":"9430_CR10","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1137\/0604033","volume":"4","author":"R. Garey","year":"1983","unstructured":"Garey, R., Johnson, D.S.: Crossing number is NP-complete. SIAM J. Algebr. Discrete Methods 4, 312\u2013316 (1983)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"9430_CR11","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1002\/jgt.20016","volume":"47","author":"L.Y. Glebsky","year":"2004","unstructured":"Glebsky, L.Y., Salazar, G.: The crossing number of cr(c m \u00d7c n ) is as conjectured for n\u2265m(m+1). J. Graph Theory 47, 53\u201372 (2004)","journal-title":"J. Graph Theory"},{"issue":"2","key":"9430_CR12","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/j.jcss.2003.07.008","volume":"68","author":"M. Grohe","year":"2004","unstructured":"Grohe, M.: Computing crossing numbers in quadratic time. J. Comput. Syst. Sci. 68(2), 285\u2013302 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"9430_CR13","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1016\/j.jctb.2005.09.009","volume":"96","author":"P. Hlin\u011bn\u00fd","year":"2006","unstructured":"Hlin\u011bn\u00fd, P.: Crossing number is hard for cubic graphs. J. Comb. Theory, Ser. B 96, 455\u2013471 (2006)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9430_CR14","first-page":"382","volume-title":"Proceedings of the 39th Annual ACM Symposium on Theory of Computing, STOC\u201907","author":"K.i. Kawarabayashi","year":"2007","unstructured":"Kawarabayashi, K.i., Reed, B.: Computing crossing number in linear time. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, STOC\u201907, pp. 382\u2013390. ACM, New York (2007)"},{"key":"9430_CR15","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":"9430_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00032","volume":"5","author":"A. Liebers","year":"2001","unstructured":"Liebers, A.: Methods for planarizing graphs\u2014a survey and annotated bibliography. J. Graph Algorithms Appl. 5, 1\u201374 (2001)","journal-title":"J. Graph Algorithms Appl."},{"key":"9430_CR17","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1007\/s00454-006-1264-9","volume":"36","author":"J. Pach","year":"2006","unstructured":"Pach, J., Radoicic, R., Tardos, G., Toth, G.: Improving the crossing lemma by finding more crossings in sparse graphs. Discrete Comput. Geom. 36, 527\u2013552 (2006)","journal-title":"Discrete Comput. Geom."},{"key":"9430_CR18","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF02086610","volume":"16","author":"J. Pach","year":"1996","unstructured":"Pach, J., Shahrokhi, F., Szegedy, M.: Applications of the crossing number. Algorithmica 16, 111\u2013117 (1996)","journal-title":"Algorithmica"},{"key":"9430_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1007\/11618058_30","volume-title":"Graph Drawing","author":"J. Pach","year":"2006","unstructured":"Pach, J., T\u00f3th, G.: Crossing number of toroidal graphs. In: Klazar, M., et al. (eds.) Graph Drawing. Lecture Notes in Computer Science, vol. 3843, pp. 334\u2013342. Springer, Berlin (2006). Also in: Topics in Discrete Mathematics, Algorithms and Combinatorics, vol.\u00a026, pp.\u00a0581\u2013590. Springer, Berlin (2006)"},{"key":"9430_CR20","series-title":"Bolyai Studies","first-page":"179","volume-title":"Intuitive Geometry","author":"F. Shahrokhi","year":"1997","unstructured":"Shahrokhi, F., S\u00fdkora, O., Sz\u00e9kely, L., Vrt\u2019o, I.: Crossing numbers: bounds and applications. In: Intuitive Geometry. Bolyai Studies, pp. 179\u2013206. Akademai Kiado, Budapest (1997)"},{"key":"9430_CR21","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., Vrt\u2019o, I.: Edge separators for graphs of bounded genus with applications. Theor. Comput. Sci. 112, 419\u2013429 (1993)","journal-title":"Theor. Comput. Sci."},{"key":"9430_CR22","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\u2019o, I.: Optimal VLSI layouts of the star graph and related networks. Integration 17, 83\u201394 (1994)","journal-title":"Integration"},{"key":"9430_CR23","unstructured":"Vrt\u2019o, I.: Crossing numbers of graphs: a bibliography. Available electronically at http:\/\/www.ifi.savba.sk\/~imrich"},{"key":"9430_CR24","first-page":"150","volume-title":"Proceedings of the 14th International Conference on Graph Drawing, GD\u201906","author":"D.R. Wood","year":"2007","unstructured":"Wood, D.R., Telle, J.A.: Planar decompositions and the crossing number of graphs with an excluded minor. In: Proceedings of the 14th International Conference on Graph Drawing, GD\u201906, pp. 150\u2013161. Springer, Berlin (2007)"},{"key":"9430_CR25","first-page":"68","volume":"3","author":"H. Yuan-qui","year":"2010","unstructured":"Yuan-qui, H., Jing, W.: Survey of the crossing number of graphs. J. East China Norm. Univ. Natur. Sci. Ed. 3, 68\u201380 (2010)","journal-title":"J. East China Norm. Univ. Natur. Sci. Ed."},{"key":"9430_CR26","doi-asserted-by":"crossref","first-page":"137","DOI":"10.4064\/fm-41-1-137-145","volume":"41","author":"K. Zarankiewicz","year":"1954","unstructured":"Zarankiewicz, K.: On a problem of P. Tur\u00e1n concerning graphs. Fundam. Math. 41, 137\u2013145 (1954)","journal-title":"Fundam. Math."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-012-9430-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-012-9430-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-012-9430-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,28]],"date-time":"2019-06-28T13:52:23Z","timestamp":1561729943000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-012-9430-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,11]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,9]]}},"alternative-id":["9430"],"URL":"https:\/\/doi.org\/10.1007\/s00454-012-9430-8","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,5,11]]}}}