{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,3]],"date-time":"2025-11-03T23:03:48Z","timestamp":1762211028216,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":43,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520049","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"343-356","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Bypassing the surface embedding: approximation schemes for network design in minor-free graphs"],"prefix":"10.1145","author":[{"given":"Vincent","family":"Cohen-Addad","sequence":"first","affiliation":[{"name":"Google Research, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Klein","author":"Abboud Amir","year":"2020","unstructured":"Amir Abboud , Vincent Cohen-Addad , and Philip N . Klein . 2020 . New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut. In STOC \u201920. Amir Abboud, Vincent Cohen-Addad, and Philip N. Klein. 2020. New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut. In STOC \u201920."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146411"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1112406"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9283-6"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646145"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/314613.314632"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258602"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.65"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027219"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2013.05.129"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9662-2"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.76"},{"volume-title":"Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. 584\u2013597","author":"Cohen-Addad V.","key":"e_1_3_2_1_13_1","unstructured":"V. Cohen-Addad , \u00c9. Colin de Verdi\u00e8re, P. N. Klein, C. Mathieu, and D. Meierfrankenfeld. 2016. Approximating connectivity domination in weighted bounded-genus graphs . In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. 584\u2013597 . V. Cohen-Addad, \u00c9. Colin de Verdi\u00e8re, P. N. Klein, C. Mathieu, and D. Meierfrankenfeld. 2016. Approximating connectivity domination in weighted bounded-genus graphs. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. 584\u2013597."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00061"},{"key":"e_1_3_2_1_15_1","volume-title":"STOC2021","author":"Cohen-Addad Vincent","year":"2021","unstructured":"Vincent Cohen-Addad , Anupam Gupta , Philip N. Klein , and Jason Li . 2021 . A Quasipolynomial (2 + epsilon)-Approximation for Planar Sparsest Cut . In STOC2021 . Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, and Jason Li. 2021. A Quasipolynomial (2 + epsilon)-Approximation for Planar Sparsest Cut. In STOC2021."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M112717X"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2019.33"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00042"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582008"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.14"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45198-3_4"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2019.6"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.141"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746564"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.52"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45022-X_73"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492665"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.4.527"},{"key":"e_1_3_2_1_29_1","volume-title":"abs\/2007.01409","author":"Karlin Anna R.","year":"2020","unstructured":"Anna R. Karlin , Nathan Klein , and Shayan Oveis Gharan . 2020. A (Slightly) Improved Approximation Algorithm for Metric TSP. CoRR , abs\/2007.01409 ( 2020 ), arxiv:2007.01409. arxiv:2007.01409 Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. 2020. A (Slightly) Improved Approximation Algorithm for Metric TSP. CoRR, abs\/2007.01409 (2020), arxiv:2007.01409. arxiv:2007.01409"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451009"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167261"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.140"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2015.02.044"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309764"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.18.1.1"},{"key":"e_1_3_2_1_36_1","volume-title":"Phillips","author":"Park James K.","year":"1993","unstructured":"James K. Park and Cynthia A . Phillips . 1993 . Finding minimum-quotient cuts in planar graphs. In STOC \u201993. James K. Park and Cynthia A. Phillips. 1993. Finding minimum-quotient cuts in planar graphs. In STOC \u201993."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/100811416"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3239560"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00359-4"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007399"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039493"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2015.12.013"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Rome Italy","acronym":"STOC '22"},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520049","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520049","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:15Z","timestamp":1750188675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520049"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":43,"alternative-id":["10.1145\/3519935.3520049","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520049","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}