{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T02:40:09Z","timestamp":1776134409884,"version":"3.50.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T00:00:00Z","timestamp":1731024000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSERC Discovery","award":["R832714"],"award-info":[{"award-number":["R832714"]}]},{"name":"Research Project","award":["N1-0218 of ARIS (Slovenia)"],"award-info":[{"award-number":["N1-0218 of ARIS (Slovenia)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"\n The main results of this paper provide an Efficient Polynomial-Time Approximation Scheme (EPTAS) for approximating the genus (and non-orientable genus) of dense graphs. By\n dense<\/jats:italic>\n we mean that\n \n \\(|E(G)|\\ge \\alpha \\, |V(G)|^2\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n for some fixed\n \n \\(\\alpha \\gt 0\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . While a constant-factor approximation is trivial for this class of graphs, approximations with factor arbitrarily close to 1 need a sophisticated algorithm and complicated mathematical justification. More precisely, we provide an algorithm that for a given (dense) graph\n G<\/jats:italic>\n of order\n n<\/jats:italic>\n and given\n \n \\(\\varepsilon \\gt 0\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , returns an integer\n g<\/jats:italic>\n such that\n G<\/jats:italic>\n has an embedding in a surface of genus\n g<\/jats:italic>\n , and this is \u025b-close to a minimum genus embedding in the sense that the minimum genus\n \n \\(\\mathsf {g}(G)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of\n G<\/jats:italic>\n satisfies:\n \n \\(\\mathsf {g}(G)\\le g\\le (1+\\varepsilon)\\mathsf {g}(G)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . The running time of the algorithm is\n \n \\(O(f(\\varepsilon)\\,n^2)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , where\n \n \\(f(\\cdot)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is an explicit function. Next, we extend this algorithm to also output an embedding (rotation system) whose genus is\n g<\/jats:italic>\n . This second algorithm is an Efficient Polynomial-time Randomized Approximation Scheme (EPRAS) and runs in time\n \n \\(O(f_1(\\varepsilon)\\,n^2)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n .\n <\/jats:p>\n \n Our algorithms are based on the analysis of minimum genus embeddings of quasirandom graphs. We use a general notion of quasirandom graphs [\n 25<\/jats:xref>\n ]. We start with a regular partition obtained via an algorithmic version of the Szemer\u00e9di Regularity Lemma (due to Frieze and Kannan [\n 17<\/jats:xref>\n ] and to Fox, Lov\u00e1sz, and Zhao [\n 14<\/jats:xref>\n ,\n 15<\/jats:xref>\n ]). We then partition the input graph into a bounded number of quasirandom subgraphs, which are preselected in such a way that they admit embeddings using as many triangles and quadrangles as faces as possible. Here we provide an \u025b-approximation\n \n \\(\\nu (G)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n for the maximum number of edge-disjoint triangles in\n G<\/jats:italic>\n . The value\n \n \\(\\nu (G)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n can be computed by solving a linear program whose size is bounded by certain value\n \n \\(f_2(\\varepsilon)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n depending only on \u025b. After solving the linear program, the genus can be approximated (see Corollary\u00a0\n 1.7<\/jats:xref>\n ). The proof of this result is long and will be of independent interest in topological graph theory.\n <\/jats:p>","DOI":"10.1145\/3690821","type":"journal-article","created":{"date-parts":[[2024,9,3]],"date-time":"2024-09-03T15:34:14Z","timestamp":1725377654000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient polynomial-time approximation scheme for the genus of dense graphs"],"prefix":"10.1145","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9954-7182","authenticated-orcid":false,"given":"Yifan","family":"Jing","sequence":"first","affiliation":[{"name":"Mathematical Institute, University of Oxford, Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7408-6148","authenticated-orcid":false,"given":"Bojan","family":"Mohar","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Simon Fraser University, Burnaby, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,11,8]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1005"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(95)00215-I"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80045-1"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.26"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00203-2"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90004-2"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2013.10.002"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02125347"},{"key":"e_1_3_2_10_2","article-title":"Computational topology of graphs on surfaces","volume":"1702","author":"Verdi\u00e8re \u00c9ric Colin de","year":"2017","unstructured":"\u00c9ric Colin de Verdi\u00e8re. 2017. Computational topology of graphs on surfaces. CoRR arXiv:1702.05358 (2017). arxiv:1702.05358http:\/\/arxiv.org\/abs\/1702.05358","journal-title":"CoRR"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_2_12_2","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-14279-6","volume-title":"Graph Theory (Fourth ed.)","author":"Diestel Reinhard","year":"2010","unstructured":"Reinhard Diestel. 2010. Graph Theory (Fourth ed.). Graduate Texts in Mathematics, Vol. 173. Springer. xviii+437 pages. 10.1007\/978-3-642-14279-6"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.4230\/DagRep.6.5.94"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1090\/jams\/876"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548317000049"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1017\/s0963548319000075"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(85)80045-7"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050052"},{"key":"e_1_3_2_19_2","volume-title":"Computers and Intractability","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S. Johnson. 1979. Computers and Intractability. W. H. Freeman and Co., San Francisco, Calif. x+338 pages. A guide to the theory of NP-completeness."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001621"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170003"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.53"},{"key":"e_1_3_2_24_2","first-page":"675","volume-title":"STOC\u201915\u2014Proceedings of the 2015 ACM Symposium on Theory of Computing","author":"Kawarabayashi Ken-ichi","year":"2015","unstructured":"Ken-ichi Kawarabayashi and Anastasios Sidiropoulos. 2015. Beyond the euler characteristic: Approximating the genus of general graphs [extended abstract]. In STOC\u201915\u2014Proceedings of the 2015 ACM Symposium on Theory of Computing. ACM, New York, 675\u2013682."},{"key":"e_1_3_2_25_2","series-title":"American Mathematical Society Colloquium Publications","doi-asserted-by":"crossref","DOI":"10.1090\/coll\/060","volume-title":"Large Networks and Graph Limits","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"2012","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz. 2012. Large Networks and Graph Limits. American Mathematical Society Colloquium Publications, Vol. 60. American Mathematical Society, Providence, RI. xiv+475 pages. 10.1090\/coll\/060"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.06.005"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.05.002"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-007-0599-6"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40328-6_18"},{"key":"e_1_3_2_30_2","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1145\/237814.237986","volume-title":"Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC\u201996)","author":"Mohar Bojan","year":"1996","unstructured":"Bojan Mohar. 1996. Embedding graphs in an arbitrary surface in linear time. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC\u201996). ACM, New York, NY, USA, 392\u2013397. 10.1145\/237814.237986"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019529248X"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.2026"},{"key":"e_1_3_2_33_2","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"Mohar B.","year":"2001","unstructured":"B. Mohar and C. Thomassen. 2001. Graphs on Surfaces. Johns Hopkins University Press, Baltimore, MD. xii+291 pages."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667060"},{"key":"e_1_3_2_35_2","doi-asserted-by":"crossref","first-page":"Paper 1.16","DOI":"10.37236\/3797","article-title":"A large set of torus obstructions and how they were discovered","volume":"25","author":"Myrvold Wendy","year":"2018","unstructured":"Wendy Myrvold and Jennifer Woodcock. 2018. A large set of torus obstructions and how they were discovered. Electron. J. Combin. 25 (2018), Paper 1.16.","journal-title":"Electron. J. Combin."},{"issue":"4","key":"e_1_3_2_36_2","first-page":"391","article-title":"Orientably simple graphs","volume":"37","author":"Parsons Torrence D.","year":"1987","unstructured":"Torrence D. Parsons, Giustina Pica, Toma\u017e Pisanski, and Aldo G. S. Ventre. 1987. Orientably simple graphs. Math. Slovaca 37, 4 (1987), 391\u2013394.","journal-title":"Math. Slovaca"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(89)90074-5"},{"key":"e_1_3_2_38_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-65759-7","volume-title":"Map Color Theorem","author":"Ringel Gerhard","year":"1974","unstructured":"Gerhard Ringel. 1974. Map Color Theorem. Springer-Verlag, New York. xii+191 pages. Die Grundlehren der mathematischen Wissenschaften, Band 209."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.12.007"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199605)8:3<161::AID-RSA1>3.0.CO;2-W"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060102"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070206"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.4064\/aa-27-1-199-245"},{"key":"e_1_3_2_45_2","series-title":"Colloq. Internat. CNRS","first-page":"399","volume-title":"Probl\u00e8mes Combinatoires et Th\u00e9orie Des Graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976)","author":"Szemer\u00e9di Endre","year":"1978","unstructured":"Endre Szemer\u00e9di. 1978. Regular partitions of graphs. In Probl\u00e8mes Combinatoires et Th\u00e9orie Des Graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976). Colloq. Internat. CNRS, Vol. 260. CNRS, Paris, 399\u2013401."},{"issue":"1","key":"e_1_3_2_46_2","first-page":"8","article-title":"Szemer\u00e9di\u2019s Regularity Lemma revisited","volume":"1","author":"Tao Terence","year":"2006","unstructured":"Terence Tao. 2006. Szemer\u00e9di\u2019s Regularity Lemma revisited. Contrib. Discrete Math. 1, 1 (2006), 8\u201328.","journal-title":"Contrib. Discrete Math."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/117"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90006-0"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1993.1016"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1996.1721"},{"key":"e_1_3_2_51_2","volume-title":"Approximation Algorithms","author":"Vazirani Vijay V.","year":"2001","unstructured":"Vijay V. Vazirani. 2001. Approximation Algorithms. Springer-Verlag, Berlin. xx+378 pages."},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/1634.322451"},{"key":"e_1_3_2_53_2","first-page":"303","article-title":"Minimal imbeddings and the genus of a graph","volume":"12","author":"Youngs J. W. T.","year":"1963","unstructured":"J. W. T. Youngs. 1963. Minimal imbeddings and the genus of a graph. J. Math. Mech. 12 (1963), 303\u2013315.","journal-title":"J. Math. Mech."},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20048"},{"key":"e_1_3_2_55_2","doi-asserted-by":"crossref","unstructured":"Gerhard Ringel and J. W. T. Youngs. 1968. Solution of the Heawood map-coloring problem. Proc. Nat. Acad. Sci. U.S.A. 60 (1968) 438\u2013445.","DOI":"10.1073\/pnas.60.2.438"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3690821","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3690821","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:58:06Z","timestamp":1750294686000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3690821"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,8]]},"references-count":54,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1145\/3690821"],"URL":"https:\/\/doi.org\/10.1145\/3690821","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,8]]},"assertion":[{"value":"2020-11-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-12","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}