{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T22:40:42Z","timestamp":1781217642460,"version":"3.54.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,1,31]],"date-time":"2022-01-31T00:00:00Z","timestamp":1643587200000},"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":["J. ACM"],"published-print":{"date-parts":[[2022,4,30]]},"abstract":"<jats:p>\n            We study the atomic embeddability testing problem, which is a common generalization of\n            <jats:bold>clustered planarity<\/jats:bold>\n            (\n            <jats:bold>c-planarity<\/jats:bold>\n            , for short) and thickenability testing, and present a polynomial-time algorithm for this problem, thereby giving the first polynomial-time algorithm for c-planarity.\n          <\/jats:p>\n          <jats:p>C-planarity was introduced in 1995 by Feng, Cohen, and Eades as a variant of graph planarity, in which the vertex set of the input graph is endowed with a hierarchical clustering and we seek an embedding (crossing free drawing) of the graph in the plane that respects the clustering in a certain natural sense. Until now, it has been an open problem whether c-planarity can be tested efficiently. The thickenability problem for simplicial complexes emerged in the topology of manifolds in the 1960s. A 2-dimensional simplicial complex is thickenable if it embeds in some orientable 3-dimensional manifold. Recently, Carmesin announced that thickenability can be tested in polynomial time.<\/jats:p>\n          <jats:p>Our algorithm for atomic embeddability combines ideas from Carmesin\u2019s work with algorithmic tools previously developed for weak embeddability testing. We express our results purely in terms of graphs on surfaces, and rely on the machinery of topological graph theory.<\/jats:p>\n          <jats:p>Finally, we give a polynomial-time reduction from atomic embeddability to thickenability thereby showing that both problems are polynomially equivalent, and show that a slight generalization of atomic embeddability to the setting in which clusters are toroidal graphs is NP-complete.<\/jats:p>","DOI":"10.1145\/3502264","type":"journal-article","created":{"date-parts":[[2022,1,31]],"date-time":"2022-01-31T17:52:59Z","timestamp":1643651579000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Atomic Embeddability, Clustered Planarity, and Thickenability"],"prefix":"10.1145","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8485-1774","authenticated-orcid":false,"given":"Radoslav","family":"Fulek","sequence":"first","affiliation":[{"name":"University of California San Diego, Stanford CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8769-3190","authenticated-orcid":false,"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[{"name":"California State University Northridge and Tufts University, Medford, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,1,31]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9918-3"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3344549"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2011.12.015"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxw035"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-00541-w"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01157400"},{"key":"e_1_3_2_8_2","series-title":"LIPIcs","first-page":"19:1\u201319:14","volume-title":"Proc. 29th Annual European Symposium on Algorithms (ESA)","author":"Bl\u00e4sius Thomas","year":"2021","unstructured":"Thomas Bl\u00e4sius, Simon D. Fink, and Ignaz Rutter. 2021. Synchronized planarity with applications to constrained planarity problems. In Proc. 29th Annual European Symposium on Algorithms (ESA)(LIPIcs, Vol. 204). Schloss Dagstuhl, 19:1\u201319:14. https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2021.19"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0301-9"},{"key":"e_1_3_2_10_2","volume-title":"Handbook of Graph Drawing and Visualization","author":"Bl\u00e4sius Thomas","year":"2013","unstructured":"Thomas Bl\u00e4sius, Stephen G. Kobourov, and Ignaz Rutter. 2013. Simultaneous embedding of planar graphs. In Handbook of Graph Drawing and Visualization, Roberto Tamassia (Ed.). Chapman and Hall\/CRC."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2738054"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.05.006"},{"key":"e_1_3_2_13_2","first-page":"2666","volume-title":"Computational Geometric and Algebraic Topology","author":"Burton Benjamin A.","year":"2015","unstructured":"Benjamin A. Burton, Arnaud de Mesmay, and Uli Wagner. 2015. Embeddability of 2-complexes. In Computational Geometric and Algebraic Topology, Benjamin Burton, Herbert Edelsbrunner, Jeff Erickson, and Stephan Tillmann (Eds.). Mathematisches Forschungsinstitut Oberwolfach, Chapter 45, 2666\u20132668. https:\/\/doi.org\/10.14760\/OWR-2015-45"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9900-0"},{"key":"e_1_3_2_15_2","unstructured":"Johannes Carmesin. 2017. Embedding simply connected 2-complexes in 3-space \u2013 II. Rotation systems. (2017). Preprint arXiv:1709.04643."},{"key":"e_1_3_2_16_2","unstructured":"Johannes Carmesin. 2017. Embedding simply connected 2-complexes in 3-space \u2013 V. A refined Kuratowski-type characterisation. (2017). Preprint arXiv:1709.04659."},{"key":"e_1_3_2_17_2","volume-title":"Embedding simply connected 2-complexes in 3-space, and further results on infinite graphs and matroids","author":"Carmesin Johannes","year":"2017","unstructured":"Johannes Carmesin. 2017. Embedding simply connected 2-complexes in 3-space, and further results on infinite graphs and matroids. Habilitationsschrift. Fachbereich Mathematik, Universit\u00e4t Hamburg. https:\/\/www.math.uni-hamburg.de\/spag\/dm\/papers\/Carmesin_Habil.pdf."},{"key":"e_1_3_2_18_2","first-page":"1655","volume-title":"Proc. 26th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Chang Hsien-Chih","year":"2015","unstructured":"Hsien-Chih Chang, Jeff Erickson, and Chao Xu. 2015. Detecting weakly simple polygons. In Proc. 26th ACM-SIAM Symposium on Discrete Algorithms (SODA). 1655\u20131670. https:\/\/doi.org\/10.1137\/1.9781611973730.110"},{"key":"e_1_3_2_19_2","first-page":"30","volume-title":"Proc. 21st Symposium on Computational Geometry (SoCG)","author":"Cortese Pier Francesco","year":"2005","unstructured":"Pier Francesco Cortese and Giuseppe Di Battista. 2005. Clustered planarity (invited lecture). In Proc. 21st Symposium on Computational Geometry (SoCG). ACM Press, 30\u201332. https:\/\/doi.org\/10.1145\/1064092.1064093"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00165"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.12.090"},{"key":"e_1_3_2_22_2","first-page":"1316","volume-title":"Proc. 29th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Mesmay Arnaud de","year":"2018","unstructured":"Arnaud de Mesmay, Yo\u2019av Rieck, Eric Sedgwick, and Martin Tancer. 2018. Embeddability in \\mathbb {R}^3 is NP-hard. In Proc. 29th ACM-SIAM Symposium on Discrete Algorithms (SODA). 1316\u20131329. https:\/\/doi.org\/10.1137\/1.9781611975031.86"},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1109\/SFCS.1989.63515","volume-title":"30th IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Battista Giuseppe Di","year":"1989","unstructured":"Giuseppe Di Battista and Roberto Tamassia. 1989. Incremental planarity testing. In 30th IEEE Symposium on Foundations of Computer Science (FOCS). 436\u2013441. https:\/\/doi.org\/10.1109\/SFCS.1989.63515"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794280736"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0030816"},{"key":"e_1_3_2_26_2","series-title":"LNCS","first-page":"213","volume-title":"Proc. 3rd European Symposium on Algorithms (ESA)","author":"Feng Qing-Wen","year":"1995","unstructured":"Qing-Wen Feng, Robert F. Cohen, and Peter Eades. 1995. Planarity for clustered graphs. In Proc. 3rd European Symposium on Algorithms (ESA)(LNCS, Vol. 979). Springer, 213\u2013226. https:\/\/doi.org\/10.1007\/3-540-60313-1_145"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-019-3905-7"},{"key":"e_1_3_2_28_2","unstructured":"Radoslav Fulek and Jan Kyn\u010dl. 2017. Hanani\u2013Tutte for approximating maps of graphs. (2017). Preprint arXiv:1705.05243."},{"key":"e_1_3_2_29_2","series-title":"LIPIcs","first-page":"39:1\u201339:15","volume-title":"Proc. 34th Symposium on Computational Geometry (SoCG)","author":"Fulek Radoslav","year":"2018","unstructured":"Radoslav Fulek and Jan Kyn\u010dl. 2018. Hanani\u2013Tutte for approximating maps of graphs. In Proc. 34th Symposium on Computational Geometry (SoCG)(LIPIcs, Vol. 99). Schloss Dagstuhl, 39:1\u201339:15. https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2018.39"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.37236\/5002"},{"key":"e_1_3_2_31_2","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1007\/3-540-36151-0_21","volume-title":"Proc. 10th Symposium on Graph Drawing","author":"Gutwenger Carsten","year":"2002","unstructured":"Carsten Gutwenger, Michael J\u00fcnger, Sebastian Leipert, Petra Mutzel, Merijam Percan, and Ren\u00e9 Weiskircher. 2002. Advances in c-planarity testing of clustered graphs. In Proc. 10th Symposium on Graph Drawing(LNCS, Vol. 2528). Springer, 220\u2013236. https:\/\/doi.org\/10.1007\/3-540-36151-0_21"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00289"},{"key":"e_1_3_2_33_2","volume-title":"Algebraic Topology","author":"Hatcher Allen","year":"2005","unstructured":"Allen Hatcher. 2005. Algebraic Topology. Cambridge University Press."},{"key":"e_1_3_2_34_2","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1145\/3357713.3384249","volume-title":"Proc. 52nd ACM Symposium on Theory of Computing (STOC)","author":"Holm Jacob","year":"2020","unstructured":"Jacob Holm and Eva Rotenberg. 2020. Fully-dynamic planarity testing in polylogarithmic time. In Proc. 52nd ACM Symposium on Theory of Computing (STOC). 167\u2013180. https:\/\/doi.org\/10.1145\/3357713.3384249"},{"key":"e_1_3_2_35_2","doi-asserted-by":"crossref","first-page":"2378","DOI":"10.1137\/1.9781611975994.146","volume-title":"Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Holm Jacob","year":"2020","unstructured":"Jacob Holm and Eva Rotenberg. 2020. Worst-Case polylog incremental SPQR-trees: Embeddings, planarity, and triconnectivity. In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA). 2378\u20132397. https:\/\/doi.org\/10.1137\/1.9781611975994.146"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65952"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-37-00336-3"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3078632"},{"issue":"2","key":"e_1_3_2_40_2","first-page":"262","article-title":"Representing homology classes by embedded circles on a compact surface","volume":"22","author":"Meeks William H.","year":"1978","unstructured":"William H. Meeks and Julie Patrusky. 1978. Representing homology classes by embedded circles on a compact surface. Illinois Journal of Mathematics 22, 2 (1978), 262\u2013269. https:\/\/doi.org\/10.1215\/ijm\/1256048735","journal-title":"Illinois Journal of Mathematics"},{"key":"e_1_3_2_41_2","unstructured":"Arnaud De Mesmay Vojt\u011bch Kalu\u017ea and Martin Tancer. 2019. Personal communication."},{"issue":"1","key":"e_1_3_2_42_2","first-page":"181","article-title":"Representing homology classes of closed orientable surfaces","volume":"61","author":"Meyerson Mark D.","year":"1976","unstructured":"Mark D. Meyerson. 1976. Representing homology classes of closed orientable surfaces. Proc. Amer. Math. Soc. 61, 1 (1976), 181\u2013182. https:\/\/doi.org\/10.1090\/S0002-9939-1976-0425967-3","journal-title":"Proc. Amer. Math. Soc."},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-8641(94)90028-0"},{"key":"e_1_3_2_44_2","series-title":"Clay Mathematics Monographs","volume-title":"Ricci Flow and the Poincar\u00e9 Conjecture","author":"Morgan John","year":"2007","unstructured":"John Morgan and Gang Tian. 2007. Ricci Flow and the Poincar\u00e9 Conjecture. Clay Mathematics Monographs, Vol. 3. AMS, Providence. 2007062016https:\/\/books.google.com\/books?id=8FctN7U85-QC."},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100043279"},{"key":"e_1_3_2_46_2","unstructured":"Grisha Perelman. 2002. The entropy formula for the Ricci flow and its geometric applications. (2002). Preprint arXiv:math\/0211159."},{"key":"e_1_3_2_47_2","unstructured":"Grisha Perelman. 2003. Finite extinction time for the solutions to the Ricci flow on certain three-manifolds. (2003). Preprint arXiv:math\/0307245."},{"key":"e_1_3_2_48_2","unstructured":"Grisha Perelman. 2003. Ricci flow with surgery on three-manifolds. (2003). Preprint arXiv:math\/0303109."},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-8641(97)00121-1"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00298"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.4064\/fm-65-3-325-343"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02305012"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-8641(03)00069-5"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4372-4"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3502264","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3502264","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:05Z","timestamp":1750191425000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3502264"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,31]]},"references-count":53,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4,30]]}},"alternative-id":["10.1145\/3502264"],"URL":"https:\/\/doi.org\/10.1145\/3502264","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,31]]},"assertion":[{"value":"2020-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}