{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T04:16:50Z","timestamp":1749010610693,"version":"3.41.0"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319388502"},{"type":"electronic","value":"9783319388519"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-38851-9_6","type":"book-chapter","created":{"date-parts":[[2016,5,31]],"date-time":"2016-05-31T15:33:54Z","timestamp":1464708834000},"page":"75-88","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Practical Method for the Minimum Genus of a Graph: Models and Experiments"],"prefix":"10.1007","author":[{"given":"Stephan","family":"Beyer","sequence":"first","affiliation":[]},{"given":"Markus","family":"Chimani","sequence":"additional","affiliation":[]},{"given":"Ivo","family":"Hedtke","sequence":"additional","affiliation":[]},{"given":"Michal","family":"Kotrb\u010d\u00edk","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,6,1]]},"reference":[{"issue":"3","key":"6_CR1","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1002\/jgt.3190100314","volume":"10","author":"D Archdeacon","year":"1986","unstructured":"Archdeacon, D.: The orientable genus is nonadditive. J. Graph Theor. 10(3), 385\u2013401 (1986)","journal-title":"J. Graph Theor."},{"key":"6_CR2","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1090\/S0002-9904-1962-10847-7","volume":"68","author":"J Battle","year":"1962","unstructured":"Battle, J., Harary, F., Kodama, Y., Youngs, J.W.T.: Additivity of the genus of a graph. Bull. Amer. Math. Soc. 68, 565\u2013568 (1962)","journal-title":"Bull. Amer. Math. Soc."},{"key":"6_CR3","unstructured":"Belov, A., Diepold, D., Heule, M.J., J\u00e4rvisalo, M. (eds.): Proceedings of SAT Competition 2014: Solver and Benchmark Descriptions. No. B-2014-2 in Series of Publications B, Department Of Computer Science, University of Helsinki (2014)"},{"issue":"2","key":"6_CR4","doi-asserted-by":"publisher","first-page":"241","DOI":"10.7155\/jgaa.00091","volume":"8","author":"JM Boyer","year":"2004","unstructured":"Boyer, J.M., Myrvold, W.J.: On the cutting edge: simplified $$O(n)$$ O ( n ) planarity by edge addition. J. Graph Algorithms Appl. 8(2), 241\u2013273 (2004)","journal-title":"J. Graph Algorithms Appl."},{"issue":"5","key":"6_CR5","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1016\/S0195-6698(88)80002-7","volume":"9","author":"MG Brin","year":"1988","unstructured":"Brin, M.G., Squier, C.C.: On the genus of $$Z_3\\times Z_3\\times Z_3$$ Z 3 \u00d7 Z 3 \u00d7 Z 3 . Eur. J. Comb. 9(5), 431\u2013443 (1988)","journal-title":"Eur. J. Comb."},{"key":"6_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/11618058_4","volume-title":"Graph Drawing","author":"C Buchheim","year":"2006","unstructured":"Buchheim, C., Ebner, D., J\u00fcnger, M., Klau, G.W., Mutzel, P., Weiskircher, R.: Exact crossing minimization. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 37\u201348. Springer, Heidelberg (2006)"},{"issue":"4","key":"6_CR7","doi-asserted-by":"publisher","first-page":"1542","DOI":"10.1137\/120864271","volume":"42","author":"S Cabello","year":"2013","unstructured":"Cabello, S., Chambers, E.W., Erickson, J.: Multiple-source shortest paths in embedded graphs. SIAM J. Comput. 42(4), 1542\u20131571 (2013)","journal-title":"SIAM J. Comput."},{"key":"6_CR8","unstructured":"Chambers, J.: Hunting for torus obstructions. M.Sc. thesis, University of Victoria (2002)"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Sidiropoulos, A.: Approximation algorithms for euler genus and related problems. In: Proceedings of FOCS 2013, pp. 167\u2013176 (2013)","DOI":"10.1109\/FOCS.2013.26"},{"issue":"7","key":"6_CR10","doi-asserted-by":"publisher","first-page":"1838","DOI":"10.1016\/j.disc.2007.12.078","volume":"309","author":"M Chimani","year":"2009","unstructured":"Chimani, M., Gutwenger, C.: Non-planar core reduction of graphs. Disc. Math. 309(7), 1838\u20131855 (2009)","journal-title":"Disc. Math."},{"key":"6_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/978-3-540-87744-8_24","volume-title":"Algorithms - ESA 2008","author":"M Chimani","year":"2008","unstructured":"Chimani, M., Mutzel, P., Bomze, I.: A new approach to exact crossing minimization. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 284\u2013296. Springer, Heidelberg (2008)"},{"issue":"2","key":"6_CR12","doi-asserted-by":"crossref","first-page":"P2.28","DOI":"10.37236\/4013","volume":"22","author":"M Conder","year":"2015","unstructured":"Conder, M., Grande, R.: On embeddings of circulant graphs. Electron. J. Comb. 22(2), P2.28 (2015)","journal-title":"Electron. J. Comb."},{"key":"6_CR13","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","volume-title":"Combinatorial Optimization","author":"WJ Cook","year":"1998","unstructured":"Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial Optimization. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1998)"},{"issue":"3","key":"6_CR14","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1021\/ci990066h","volume":"40","author":"M Deza","year":"2000","unstructured":"Deza, M., Fowler, P.W., Rassat, A., Rogers, K.M.: Fullerenes as tilings of surfaces. J. Chem. Inf. Comput. Sci. 40(3), 550\u2013558 (2000)","journal-title":"J. Chem. Inf. Comput. Sci."},{"issue":"6","key":"6_CR15","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1142\/S0218195900000358","volume":"10","author":"G Battista Di","year":"2000","unstructured":"Di Battista, G., Garg, A., Liotta, G., Parise, A., Tamassia, R., Tassinari, E., Vargiu, F., Vismara, L.: Drawing directed acyclic graphs: an experimental study. Int. J. Comput. Geom. Appl. 10(6), 623\u2013648 (2000)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"5\u20136","key":"6_CR16","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/S0925-7721(96)00005-3","volume":"7","author":"G Battista Di","year":"1997","unstructured":"Di Battista, G., Garg, A., Liotta, G., Tamassia, R., Tassinari, E., Vargiu, F.: An experimental comparison of four graph drawing algorithms. Comput. Geom. 7(5\u20136), 303\u2013325 (1997)","journal-title":"Comput. Geom."},{"key":"6_CR17","doi-asserted-by":"crossref","unstructured":"Djidjev, H., Reif, J.: An efficient algorithm for the genus problem with explicit construction of forbidden subgraphs. In: Proceedings of STOC 1991, pp. 337\u2013347. ACM (1991)","DOI":"10.1145\/103418.103456"},{"key":"6_CR18","first-page":"646","volume":"7","author":"J Edmonds","year":"1960","unstructured":"Edmonds, J.: A combinatorial representation for polyhedral surfaces. Not. Amer. Math. Soc. 7, 646 (1960)","journal-title":"Not. Amer. Math. Soc."},{"key":"6_CR19","doi-asserted-by":"crossref","unstructured":"Erickson, J., Fox, K., Nayyeri, A.: Global minimum cuts in surface embedded graphs. In: Proceedings of SODA 2012, pp. 1309\u20131318. SIAM (2012)","DOI":"10.1137\/1.9781611973099.103"},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"Filotti, I.S.: An efficient algorithm for determining whether a cubic graph is toroidal. In: Proceedings of STOC 1978, pp. 133\u2013142. ACM (1978)","DOI":"10.1145\/800133.804341"},{"key":"6_CR21","doi-asserted-by":"crossref","unstructured":"Filotti, I.S., Miller, G.L., Reif, J.: On determining the genus of a graph in $$O(V^{O(G)})$$ O ( V O ( G ) ) steps. In: Proceedings of STOC 1979, pp. 27\u201337. ACM (1979)","DOI":"10.1145\/800135.804395"},{"key":"6_CR22","volume-title":"Computers and Intractability. A Guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the theory of NP-completeness. Bell Telephone Laboratories, New York (1979)"},{"key":"6_CR23","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","volume-title":"Topological Graph Theory","author":"JL Gross","year":"1987","unstructured":"Gross, J.L., Tucker, T.W.: Topological Graph Theory. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1987)"},{"key":"6_CR24","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/BF01203357","volume":"38","author":"L Heffter","year":"1891","unstructured":"Heffter, L.: Ueber das Problem der Nachbargebiete. Math. Ann. 38, 477\u2013508 (1891)","journal-title":"Math. Ann."},{"key":"6_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1007\/3-540-59408-6_64","volume-title":"Integer Programming and Combinatorial Optimization","author":"M Juvan","year":"1995","unstructured":"Juvan, M., Marin\u010dek, J., Mohar, B.: Embedding graphs in the torus in linear time. In: Balas, E., Clausen, J. (eds.) IPCO 1995. LNCS, vol. 920, pp. 360\u2013363. Springer, Heidelberg (1995)"},{"key":"6_CR26","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Mohar, B., Reed, B.: A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width. In: Proceedings of FOCS 2008, pp. 771\u2013780 (2008)","DOI":"10.1109\/FOCS.2008.53"},{"key":"6_CR27","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Sidiropoulos, A.: Beyond the euler characteristic: approximating the genus of general graphs. In: Proceedings of STOC 2015. ACM (2015)","DOI":"10.1145\/2746539.2746583"},{"issue":"4","key":"6_CR28","doi-asserted-by":"crossref","first-page":"P4.2","DOI":"10.37236\/2951","volume":"22","author":"M Kotrb\u010d\u00edk","year":"2015","unstructured":"Kotrb\u010d\u00edk, M., Pisanski, T.: Genus of cartesian product of triangles. Electron. J. Comb. 22(4), P4.2 (2015)","journal-title":"Electron. J. Comb."},{"issue":"3\u20134","key":"6_CR29","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/j.ejc.2004.01.015","volume":"26","author":"D Maru\u0161i\u010d","year":"2005","unstructured":"Maru\u0161i\u010d, D., Pisanski, T., Wilson, S.: The genus of the GRAY graph is 7. Eur. J. Comb. 26(3\u20134), 377\u2013385 (2005)","journal-title":"Eur. J. Comb."},{"key":"6_CR30","doi-asserted-by":"crossref","unstructured":"Mohar, B.: Embedding graphs in an arbitrary surface in linear time. In: Proceedings of STOC 1996, pp. 392\u2013397. ACM (1996)","DOI":"10.1145\/237814.237986"},{"issue":"1","key":"6_CR31","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0012-365X(85)90197-9","volume":"56","author":"B Mohar","year":"1985","unstructured":"Mohar, B., Pisanski, T., \u0160koviera, M., White, A.: The cartesian product of 3 triangles can be embedded into a surface of genus 7. Disc. Math. 56(1), 87\u201389 (1985)","journal-title":"Disc. Math."},{"key":"6_CR32","series-title":"Johns Hopkins Studies in the Mathematical Sciences","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 Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2001)"},{"issue":"2","key":"6_CR33","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1016\/j.jcss.2010.06.002","volume":"77","author":"W Myrvold","year":"2011","unstructured":"Myrvold, W., Kocay, W.: Errors in graph embedding algorithms. J. Comput. Syst. Sci. 77(2), 430\u2013438 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-65759-7","volume-title":"Map Color Theorem","author":"G Ringel","year":"1974","unstructured":"Ringel, G.: Map Color Theorem. Springer, Heidelberg (1974)"},{"key":"6_CR35","unstructured":"Schmidt, P.: Algoritmick\u00e9 vlastnosti vnoren\u00ed grafov do pl\u00f4ch. B.Sc. thesis, Comenius University (2012). In Slovak"},{"key":"6_CR36","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1016\/0196-6774(89)90006-0","volume":"10","author":"C Thomassen","year":"1989","unstructured":"Thomassen, C.: The graph genus problem is NP-complete. J. Algorithms 10, 568\u2013576 (1989)","journal-title":"J. Algorithms"},{"key":"6_CR37","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1006\/jctb.1996.1721","volume":"69","author":"C Thomassen","year":"1997","unstructured":"Thomassen, C.: The graph genus problem is NP-complete for cubic graphs. J. Comb. Theor. Ser. B 69, 52\u201358 (1997)","journal-title":"J. Comb. Theor. Ser. B"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-38851-9_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,3]],"date-time":"2025-06-03T20:05:41Z","timestamp":1748981141000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-38851-9_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319388502","9783319388519"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-38851-9_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"1 June 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}