{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:58:26Z","timestamp":1787385506086,"version":"build-2736575974"},"reference-count":49,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/100000008","name":"David and Lucile Packard Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000008","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1016684"],"award-info":[{"award-number":["CCF-1016684"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0915984"],"award-info":[{"award-number":["CCF-0915984"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0915519"],"award-info":[{"award-number":["CCF-0915519"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>The Euler genus of a graph is a fundamental and well-studied parameter in graph theory and topology. Computing it has been shown to be NP-hard by Thomassen [ J. Algorithms, 10 (1989), pp. 568--576; J. Combin. Theory, Ser. B, 57 (1993), pp. 196--206], and it is known to be fixed-parameter tractable. However, the approximability of the Euler genus is wide open. While the existence of an $O(1)$-approximation is not ruled out, only an $O(\\sqrt{n})$-approximation [J. Chen, S. P. Kanchi, and A. Kanevsky, Inform. Process. Lett., 61 (1997), pp. 317--322] is known even in bounded-degree graphs. In this paper we give a polynomial-time algorithm which, given a bounded-degree graph of Euler genus $g$, computes a drawing in a surface of Euler genus $g^{O(1)} \\cdot \\log^{O(1)} n$. Combined with the upper bound from [J. Chen, S. P. Kanchi, and A. Kanevsky, Inform. Process. Lett., 61 (1997), pp. 317--322], our result also implies a $O(n^{1\/2 - \\alpha})$-approximation for some constant $\\alpha&gt;0$. Using our algorithm for approximating the Euler genus as a subroutine, we obtain, in a uniform fashion, algorithms with approximation ratios of the form $\\mathsf{OPT}^{O(1)} \\cdot \\log^{O(1)} n$ for several related problems on bounded-degree graphs. These include the problems of orientable genus, crossing number, and planar edge and vertex deletion. Our algorithm and proof of correctness for the crossing number problem are simpler compared to the long and difficult proof in the recent breakthrough by Chuzhoy [ Proceedings of the ACM Symposium on Theory of Computing, 2011, pp. 303--312], while essentially obtaining a qualitatively similar result. For planar edge and vertex deletion problems our results are the first to obtain a bound of the form $\\operatorname{poly}(\\mathsf{OPT},\\log n)$. We also highlight some further applications of our results in the design of algorithms for graphs with small genus. Many such algorithms require that a drawing of the graph is given as part of the input. Our results imply that in several interesting cases, we can implement such algorithms even when the drawing is unknown.<\/jats:p>","DOI":"10.1137\/14099228x","type":"journal-article","created":{"date-parts":[[2018,8,14]],"date-time":"2018-08-14T10:41:16Z","timestamp":1534243276000},"page":"1610-1643","source":"Crossref","is-referenced-by-count":3,"title":["Approximation Algorithms for Euler Genus and Related Problems"],"prefix":"10.1137","volume":"47","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anastasios","family":"Sidiropoulos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,8,14]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190050305"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90071-0"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1996.0016"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9440-6"},{"key":"atypb5","first-page":"123","volume":"7","author":"Cabello S.","year":"2016","journal-title":"J. Comput. Geom."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1292-5"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/120872310"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0920"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"C. Chekuri, S. Khanna, and F. B. Shepherd,\n                      Edge-disjoint paths in planar graphs\n                      , in proceedings of the 45th Symposium on Foundations of Computer Science, 2004, Rome, IEEE Computer Society, pp. 71-80,https:\/\/doi.org\/10.1109\/FOCS.2004.27.","DOI":"10.1109\/FOCS.2004.27"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00203-2"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-016-0030-z"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"J. Chuzhoy,\n                      An algorithm for the graph crossing number problem\n                      , in Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011, San Jose, CA, pp. 303-312,https:\/\/doi.org\/10.1145\/1993636.1993678.","DOI":"10.1145\/1993636.1993678"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"J. Chuzhoy, Y. Makarychev, and A. Sidiropoulos,\n                      On graph crossing number and edge planarization\n                      , in Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, 2011, D. Randall, ed., pp. 1050-1069,https:\/\/doi.org\/10.1137\/1.9781611973082.80.","DOI":"10.1137\/1.9781611973082.80"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.37236\/3872"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"J. Erickson, K. Fox, and L. Lkhamsuren,\n                      Holiest minimum-cost paths and flows in surface graphs\n                      , in Proceedings of the 50th Annual ACM Symposium on Theory of Computing, 2018.","DOI":"10.1145\/3188745.3188904"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-2948-z"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"J. Erickson and A. Sidiropoulos,\n                      A near-optimal approximation algorithm for asymmetric TSP on embedded graphs\n                      , in Proceedings of the 30th Annual Symposium on Computational Geometry, Kyoto, Japan, 2014, ACM, S. Cheng and O. Devillers, eds., p. 130,https:\/\/doi.org\/10.1145\/2582112.2582136.","DOI":"10.1145\/2582112.2582136"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-010-9241-8"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2004.06.019"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00370-6"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/05064299X"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190200305"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"K. Fox,\n                      Shortest non-trivial cycles in directed and undirected surface graphs\n                      , in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, 2013, S. Khanna, ed., SIAM, pp. 352-364,https:\/\/doi.org\/10.1137\/1.9781611973105.26.","DOI":"10.1137\/1.9781611973105.26"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"S. Oveis Gharan and A. Saberi,\n                      The asymmetric traveling salesman problem on graphs with bounded genus\n                      , in Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, 2011, D. Randall, ed., pp. 967-975,https:\/\/doi.org\/10.1137\/1.9781611973082.75.","DOI":"10.1137\/1.9781611973082.75"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"H. H. Glover, J. P. Huneke, and C. San Wang,\n                      103 graphs that are irreducible for the projective plane\n                      , J. Combin. Theory Series B, 27 (1979), pp. 332-370.","DOI":"10.1016\/0095-8956(79)90022-4"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.008"},{"key":"atypb28","unstructured":"J. Gross and T. Tucker,\n                      Topological graph theory\n                      , Dover Publications, Mineola, NY, 2001."},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.07.017"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"atypb31","first-page":"771","author":"Kawarabayashi K.","year":"2008","journal-title":"PA"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"K. Kawarabayashi and B. A. Reed,\n                      Computing crossing number in linear time\n                      , in Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, CA, 2007, D. S. Johnson and U. Feige, eds., pp. 382-390,https:\/\/doi.org\/10.1145\/1250790.1250848.","DOI":"10.1145\/1250790.1250848"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"Y. Makarychev, A. Nayyeri, and A. Sidiropoulos,\n                      A pseudo-approximation for the genus of Hamiltonian graphs\n                      , in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings, P. Raghavendra, S. Raskhodnikova, K. Jansen, and J. D. P. Rolim, eds., Lecture Notes in Comput. Sci. 8096, Springer, New York, 2013, pp. 244-259,https:\/\/doi.org\/10.1007\/978-3-642-40328-6_18.","DOI":"10.1007\/978-3-642-40328-6_18"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1992-076-8"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019529248X"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.2026"},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"B. Mohar and C. Thomassen,\n                      Graphs on Surfaces\n                      , Johns Hopkins University Press, Baltimone, MD, 2001.","DOI":"10.56021\/9780801866890"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199706)25:2<153::AID-JGT7>3.0.CO;2-L"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90121-F"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1073"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215352"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90006-0"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90115-G"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1993.1016"},{"key":"atypb48","unstructured":"S. Tragoudas,\n                      VLSI Partitioning Approximation Algorithms Based on Multicommodity Flow and Other Techniques\n                      , Ph.D. thesis, University of Texas at Dallas, Richardson, TX, 1991."},{"key":"atypb49","unstructured":"A. White,\n                      Graphs of Groups on Surfaces: Interactions and Models\n                      , Elsevier, New York, 2001."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/14099228X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:14:51Z","timestamp":1787339691000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/14099228X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":49,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/14099228X"],"URL":"https:\/\/doi.org\/10.1137\/14099228x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}