{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:41:19Z","timestamp":1725745279121},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642403279"},{"type":"electronic","value":"9783642403286"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40328-6_18","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T13:17:34Z","timestamp":1376659054000},"page":"244-259","source":"Crossref","is-referenced-by-count":2,"title":["A Pseudo-approximation for the Genus of Hamiltonian Graphs"],"prefix":"10.1007","author":[{"given":"Yury","family":"Makarychev","sequence":"first","affiliation":[]},{"given":"Amir","family":"Nayyeri","sequence":"additional","affiliation":[]},{"given":"Anastasios","family":"Sidiropoulos","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"18_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/978-3-642-22006-7_11","volume-title":"Automata, Languages and Programming","author":"M. Chimani","year":"2011","unstructured":"Chimani, M., Hlin\u011bn\u00fd, P.: A tighter insertion-based approximation of the crossing number. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol.\u00a06755, pp. 122\u2013134. Springer, Heidelberg (2011)"},{"doi-asserted-by":"crossref","unstructured":"Chuzhoy, J.: An algorithm for the graph crossing number problem. In: STOC, pp. 303\u2013312 (2011)","key":"18_CR2","DOI":"10.1145\/1993636.1993678"},{"issue":"6","key":"18_CR3","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/S0020-0190(97)00203-2","volume":"61","author":"J. Chen","year":"1997","unstructured":"Chen, J., Kanchi, S.P., Kanevsky, A.: A note on approximating graph genus. Inf. Process. Lett.\u00a061(6), 317\u2013322 (1997)","journal-title":"Inf. Process. Lett."},{"doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Makarychev, Y., Sidiropoulos, A.: On graph crossing number and edge planarization. In: SODA, pp. 1050\u20131069 (2011)","key":"18_CR4","DOI":"10.1137\/1.9781611973082.80"},{"unstructured":"Chekuri, C., Sidiropoulos, A.: Approximating the genus of a graph. Manuscript","key":"18_CR5"},{"doi-asserted-by":"crossref","unstructured":"Filotti, I.S., Miller, G.L., Reif, J.H.: On determining the genus of a graph in O(v\n                  \n                    O(g)) steps. In: STOC, pp. 27\u201337 (1979)","key":"18_CR6","DOI":"10.1145\/800135.804395"},{"unstructured":"Gross, J.L., Tucker, T.W.: Topological graph theory. Dover Publications (2001)","key":"18_CR7"},{"unstructured":"Hatcher, A.: Algebraic Topology. Cambridge University Press (2002)","key":"18_CR8"},{"issue":"4","key":"18_CR9","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"Hopcroft, J., Tarjan, R.: Efficient planarity testing. J. ACM\u00a021(4), 549\u2013568 (1974)","journal-title":"J. ACM"},{"unstructured":"Ken-ichi, Mohar, B., Reed, B.A.: A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width. In: FOCS, pp. 771\u2013780 (2008)","key":"18_CR10"},{"issue":"6","key":"18_CR11","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"F.T. Leighton","year":"1999","unstructured":"Leighton, F.T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM\u00a046(6), 787\u2013832 (1999)","journal-title":"J. ACM"},{"key":"18_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1007\/978-3-642-00219-9_42","volume-title":"Graph Drawing","author":"M. Chimani","year":"2009","unstructured":"Chimani, M., Hlin\u011bn\u00fd, P., Mutzel, P.: Approximating the crossing number of apex graphs. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol.\u00a05417, pp. 432\u2013434. Springer, Heidelberg (2009)"},{"issue":"2","key":"18_CR13","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0095-8956(92)90015-P","volume":"56","author":"A. Malnic","year":"1992","unstructured":"Malnic, A., Mohar, B.: Generating locally cyclic triangulations of surfaces. Journal of Combinatorial Theory, Series B\u00a056(2), 147\u2013164 (1992)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"1","key":"18_CR14","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1137\/S089548019529248X","volume":"12","author":"B. Mohar","year":"1999","unstructured":"Mohar, B.: A linear time algorithm for embedding graphs in an arbitrary surface. SIAM J. Discrete Math.\u00a012(1), 6\u201326 (1999)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"18_CR15","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1006\/jctb.2000.2026","volume":"82","author":"B. Mohar","year":"2001","unstructured":"Mohar, B.: Face covers and the genus problem for apex graphs. Journal of Combinatorial Theory, Series B\u00a082(1), 102\u2013117 (2001)","journal-title":"Journal of Combinatorial Theory, Series B"},{"unstructured":"Mohar, B., Thomassen, C.: Graphs on surfaces. Johns Hopkins studies in the mathematical sciences. Johns Hopkins University Press (2001)","key":"18_CR16"},{"doi-asserted-by":"crossref","unstructured":"Hlinen\u00fd, P., Chimani, M.: Approximating the crossing number of graphs embeddable in any orientable surface. In: SODA, pp. 918\u2013927 (2010)","key":"18_CR17","DOI":"10.1137\/1.9781611973075.74"},{"issue":"2","key":"18_CR18","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0095-8956(90)90121-F","volume":"48","author":"N. Robertson","year":"1990","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. VIII. A Kuratowski theorem for general surfaces. J. Comb. Theory, Ser. B\u00a048(2), 255\u2013288 (1990)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"4","key":"18_CR19","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\u00a010(4), 568\u2013576 (1989)","journal-title":"J. Algorithms"},{"issue":"2","key":"18_CR20","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1006\/jctb.1993.1016","volume":"57","author":"C. Thomassen","year":"1993","unstructured":"Thomassen, C.: Triangulating a surface with a prescribed graph. J. Comb. Theory, Ser. B\u00a057(2), 196\u2013206 (1993)","journal-title":"J. Comb. Theory, Ser. B"},{"unstructured":"White, A.T.: Graphs of groups on surfaces: interactions and models. North-Holland mathematics studies. Elsevier (2001)","key":"18_CR21"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40328-6_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T17:51:35Z","timestamp":1558029095000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40328-6_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403279","9783642403286"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40328-6_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}