{"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":1781217642513,"version":"3.54.1"},"reference-count":73,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2021,6,8]],"date-time":"2021-06-08T00:00:00Z","timestamp":1623110400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,8]],"date-time":"2021-06-08T00:00:00Z","timestamp":1623110400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"H2020 Marie Sklodowska-Curie Actions","award":["734922"],"award-info":[{"award-number":["734922"]}]},{"name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e1 e della Ricerca","award":["PRIN 20174LF3T8"],"award-info":[{"award-number":["PRIN 20174LF3T8"]}]},{"name":"National Science Foundation","award":["CCF-1618301"],"award-info":[{"award-number":["CCF-1618301"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1616248"],"award-info":[{"award-number":["CCF-1616248"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1815073"],"award-info":[{"award-number":["1815073"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Zuckerman STEM Leadership Program"},{"DOI":"10.13039\/100008991","name":"Universit\u00e0 degli Studi Roma Tre","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100008991","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>For a <jats:italic>clustered graph<\/jats:italic>, i.e, a graph whose vertex set is recursively partitioned into clusters, the <jats:sc>C-Planarity Testing<\/jats:sc> problem asks whether it is possible to find a planar embedding of the graph and a representation of each cluster as a region homeomorphic to a closed disk such that (1)\u00a0the subgraph induced by each cluster is drawn in the interior of the corresponding disk, (2)\u00a0each edge intersects any disk at most once, and (3)\u00a0the nesting between clusters is reflected by the representation, i.e., child clusters are properly contained in their parent cluster. The computational complexity of this problem, whose study has been central to the theory of graph visualization since its introduction in 1995 [Feng, Cohen, and Eades, <jats:italic>Planarity for clustered graphs<\/jats:italic>, ESA\u201995], has only been recently settled [Fulek and T\u00f3th, <jats:italic>Atomic Embeddability, Clustered Planarity, and Thickenability<\/jats:italic>, to appear at SODA\u201920]. Before such a breakthrough, the complexity question was still unsolved even when the graph has a prescribed planar embedding, i.e, for <jats:italic>embedded clustered graphs<\/jats:italic>. We show that the <jats:sc>C-Planarity Testing<\/jats:sc> problem admits a single-exponential single-parameter FPT (resp., XP) algorithm for embedded flat (resp., non-flat) clustered graphs, when parameterized by the carving-width of the dual graph of the input. These are the first FPT and XP algorithms for this long-standing open problem with respect to a single notable graph-width parameter. Moreover, the polynomial dependency of our FPT algorithm is smaller than the one of the algorithm by Fulek and T\u00f3th. In particular, our algorithm runs in quadratic time for flat instances of bounded treewidth and bounded face size. To further strengthen the relevance of this result, we show that an algorithm with running time <jats:italic>O<\/jats:italic>(<jats:italic>r<\/jats:italic>(<jats:italic>n<\/jats:italic>)) for flat instances whose underlying graph has pathwidth 1 would result in an algorithm with running time <jats:italic>O<\/jats:italic>(<jats:italic>r<\/jats:italic>(<jats:italic>n<\/jats:italic>)) for flat instances and with running time <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(r(n^2) + n^2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>r<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msup>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mn>2<\/mml:mn>\n                      <\/mml:msup>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for general, possibly non-flat, instances.<\/jats:p>","DOI":"10.1007\/s00453-021-00839-2","type":"journal-article","created":{"date-parts":[[2021,6,8]],"date-time":"2021-06-08T11:27:20Z","timestamp":1623151640000},"page":"2471-2502","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2396-5174","authenticated-orcid":false,"given":"Giordano","family":"Da Lozzo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Eppstein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael T.","family":"Goodrich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Siddharth","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,6,8]]},"reference":[{"key":"839_CR1","doi-asserted-by":"publisher","unstructured":"Adler, I., Bui-Xuan, B., Rabinovich, Y., Renault, G., Telle, J.A., Vatshelle, M.: On the boolean-width of a graph: structure and applications. In: D.M. Thilikos (ed.) WG 2010, LNCS, vol. 6410, pp. 159\u2013170 (2010). https:\/\/doi.org\/10.1007\/978-3-642-16926-7_16","DOI":"10.1007\/978-3-642-16926-7_16"},{"key":"839_CR2","doi-asserted-by":"publisher","unstructured":"Akitaya, H.A., Fulek, R., T\u00f3th, C.D.: Recognizing weak embeddings of graphs. In: A.\u00a0Czumaj (ed.) SODA\u00a0\u201918, pp. 274\u2013292. SIAM (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.20","DOI":"10.1137\/1.9781611975031.20"},{"issue":"12","key":"839_CR3","doi-asserted-by":"publisher","first-page":"1831","DOI":"10.1093\/comjnl\/bxw035","volume":"59","author":"P Angelini","year":"2016","unstructured":"Angelini, P., Da Lozzo, G.: SEFE = C-planarity? Comput. J. 59(12), 1831\u20131838 (2016). https:\/\/doi.org\/10.1093\/comjnl\/bxw035","journal-title":"Comput. J."},{"issue":"6","key":"839_CR4","doi-asserted-by":"publisher","first-page":"2484","DOI":"10.1007\/s00453-018-00541-w","volume":"81","author":"P Angelini","year":"2019","unstructured":"Angelini, P., Da Lozzo, G.: Clustered planarity with pipes. Algorithmica 81(6), 2484\u20132526 (2019). https:\/\/doi.org\/10.1007\/s00453-018-00541-w","journal-title":"Algorithmica"},{"key":"839_CR5","doi-asserted-by":"publisher","unstructured":"Angelini, P., Da Lozzo, G.: Beyond clustered planar graphs. In: S.\u00a0Hong, T.\u00a0Tokuyama (eds.) Beyond Planar Graphs, Communications of NII Shonan Meetings, pp. 211\u2013235. Springer (2020). https:\/\/doi.org\/10.1007\/978-981-15-6533-5_12","DOI":"10.1007\/978-981-15-6533-5_12"},{"issue":"4","key":"839_CR6","doi-asserted-by":"publisher","first-page":"1022","DOI":"10.1007\/s00453-016-0128-9","volume":"77","author":"P Angelini","year":"2017","unstructured":"Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F.: Strip planarity testing for embedded planar graphs. Algorithmica 77(4), 1022\u20131059 (2017). https:\/\/doi.org\/10.1007\/s00453-016-0128-9","journal-title":"Algorithmica"},{"issue":"2","key":"839_CR7","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.comgeo.2014.08.001","volume":"48","author":"P Angelini","year":"2015","unstructured":"Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M., Roselli, V.: Relaxing the constraints of clustered planarity. Comput. Geom. 48(2), 42\u201375 (2015). https:\/\/doi.org\/10.1016\/j.comgeo.2014.08.001","journal-title":"Comput. Geom."},{"issue":"4","key":"839_CR8","doi-asserted-by":"publisher","first-page":"731","DOI":"10.7155\/jgaa.00437","volume":"21","author":"P Angelini","year":"2017","unstructured":"Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M., Rutter, I.: Intersection-link representations of graphs. J. Graph Algorithms Appl. 21(4), 731\u2013755 (2017). https:\/\/doi.org\/10.7155\/jgaa.00437","journal-title":"J. Graph Algorithms Appl."},{"key":"839_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2014.12.019","volume":"571","author":"P Angelini","year":"2015","unstructured":"Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Roselli, V.: The importance of being proper: (in clustered-level planarity and T-level planarity). Theor. Comput. Sci. 571, 1\u20139 (2015). https:\/\/doi.org\/10.1016\/j.tcs.2014.12.019","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"839_CR10","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/s00454-010-9302-z","volume":"45","author":"P Angelini","year":"2011","unstructured":"Angelini, P., Frati, F., Kaufmann, M.: Straight-line rectangular drawings of clustered graphs. Discrete Comput. Geom. 45(1), 88\u2013140 (2011). https:\/\/doi.org\/10.1007\/s00454-010-9302-z","journal-title":"Discrete Comput. Geom."},{"issue":"6","key":"839_CR11","doi-asserted-by":"publisher","first-page":"1057","DOI":"10.7155\/jgaa.00450","volume":"21","author":"JC Athenst\u00e4dt","year":"2017","unstructured":"Athenst\u00e4dt, J.C., Cornelsen, S.: Planarity of overlapping clusterings including unions of two partitions. J. Graph Algorithms Appl. 21(6), 1057\u20131089 (2017). https:\/\/doi.org\/10.7155\/jgaa.00450","journal-title":"J. Graph Algorithms Appl."},{"key":"839_CR12","doi-asserted-by":"publisher","unstructured":"Athenst\u00e4dt, J.C., Hartmann, T., N\u00f6llenburg, M.: Simultaneous embeddability of two partitions. In: C.A. Duncan, A.\u00a0Symvonis (eds.) Graph Drawing\u201422nd International Symposium, GD 2014, W\u00fcrzburg, Germany, September 24\u201326, 2014, Revised Selected Papers, Lecture Notes in Computer Science, vol. 8871, pp. 64\u201375. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-662-45803-7_6","DOI":"10.1007\/978-3-662-45803-7_6"},{"key":"839_CR13","doi-asserted-by":"crossref","unstructured":"Biedl, T.: Drawing planar partitions III: Two Constrained Embedding Problems. Tech. Report RRR 13-98, Rutcor Research Report (1998)","DOI":"10.1145\/276884.276917"},{"issue":"4\u20135","key":"839_CR14","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1142\/S0218195913600091","volume":"23","author":"TC Biedl","year":"2013","unstructured":"Biedl, T.C., Vatshelle, M.: The point-set embeddability problem for plane graphs. Int. J. Comput. Geometry Appl. 23(4\u20135), 357\u2013396 (2013). https:\/\/doi.org\/10.1142\/S0218195913600091","journal-title":"Int. J. Comput. Geometry Appl."},{"issue":"1","key":"839_CR15","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1287\/moor.13.1.99","volume":"13","author":"RE Bixby","year":"1988","unstructured":"Bixby, R.E., Wagner, D.K.: An almost linear-time algorithm for graph realization. Math. Oper. Res. 13(1), 99\u2013123 (1988). https:\/\/doi.org\/10.1287\/moor.13.1.99","journal-title":"Math. Oper. Res."},{"key":"839_CR16","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1016\/j.tcs.2015.10.011","volume":"609","author":"T Bl\u00e4sius","year":"2016","unstructured":"Bl\u00e4sius, T., Rutter, I.: A new perspective on clustered planarity as a combinatorial embedding problem. Theor. Comput. Sci. 609, 306\u2013315 (2016). https:\/\/doi.org\/10.1016\/j.tcs.2015.10.011","journal-title":"Theor. Comput. Sci."},{"key":"839_CR17","unstructured":"Borradaile, G., Erickson, J., Le, H., Weber, R.: Embedded-width: a variant of treewidth for plane graphs (2017). arXiv:1703.07532"},{"key":"839_CR18","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/S1571-0653(04)00353-1","volume":"10","author":"V Bouchitt\u00e9","year":"2001","unstructured":"Bouchitt\u00e9, V., Mazoit, F., Todinca, I.: Treewidth of planar graphs: connections with duality. ENDM 10, 34\u201338 (2001). https:\/\/doi.org\/10.1016\/S1571-0653(04)00353-1","journal-title":"ENDM"},{"key":"839_CR19","doi-asserted-by":"publisher","unstructured":"Brandenburg, F., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Liotta, G., Mutzel, P.: Selected open problems in graph drawing. In: G.\u00a0Liotta (ed.) GD\u00a0\u201903, LNCS, vol. 2912, pp. 515\u2013539. Springer (2003). https:\/\/doi.org\/10.1007\/978-3-540-24595-7_55","DOI":"10.1007\/978-3-540-24595-7_55"},{"key":"839_CR20","doi-asserted-by":"publisher","unstructured":"Brandes, U., Cornelsen, S., Pampel, B., Sallaberry, A.: Blocks of hypergraphs-applied to hypergraphs and outerplanarity. In: C.S. Iliopoulos, W.F. Smyth (eds.) Combinatorial Algorithms\u201421st International Workshop, IWOCA 2010, London, UK, July 26\u201328, 2010, Revised Selected Papers, Lecture Notes in Computer Science, vol. 6460, pp. 201\u2013211. Springer (2010). https:\/\/doi.org\/10.1007\/978-3-642-19222-7_21","DOI":"10.1007\/978-3-642-19222-7_21"},{"key":"839_CR21","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1016\/j.jda.2011.12.009","volume":"14","author":"U Brandes","year":"2012","unstructured":"Brandes, U., Cornelsen, S., Pampel, B., Sallaberry, A.: Path-based supports for hypergraphs. J. Discrete Algorithms 14, 248\u2013261 (2012). https:\/\/doi.org\/10.1016\/j.jda.2011.12.009","journal-title":"J. Discrete Algorithms"},{"key":"839_CR22","doi-asserted-by":"publisher","unstructured":"Brandes, U., Lerner, J.: Visual analysis of controversy in user-generated encyclopedias. In: IEEE VAST\u00a0\u201907, pp. 179\u2013186. IEEE Computer Society (2007). https:\/\/doi.org\/10.1109\/VAST.2007.4389012","DOI":"10.1109\/VAST.2007.4389012"},{"issue":"4","key":"839_CR23","doi-asserted-by":"publisher","first-page":"533","DOI":"10.7155\/jgaa.00237","volume":"15","author":"K Buchin","year":"2011","unstructured":"Buchin, K., van Kreveld, M.J., Meijer, H., Speckmann, B., Verbeek, K.: On planar supports for hypergraphs. J. Graph Algorithms Appl. 15(4), 533\u2013549 (2011). https:\/\/doi.org\/10.7155\/jgaa.00237","journal-title":"J. Graph Algorithms Appl."},{"key":"839_CR24","unstructured":"Carmesin, J.: Embedding simply connected 2-complexes in 3-space\u2014v. A refined kuratowski-type characterisation (2017)"},{"key":"839_CR25","doi-asserted-by":"publisher","unstructured":"Chimani, M., Di Battista, G., Frati, F., Klein, K.: Advances on testing c-planarity of embedded flat clustered graphs. In: C.A. Duncan, A.\u00a0Symvonis (eds.) GD\u00a0\u201914, LNCS, vol. 8871, pp. 416\u2013427. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-662-45803-7_35","DOI":"10.1007\/978-3-662-45803-7_35"},{"key":"839_CR26","doi-asserted-by":"publisher","unstructured":"Chimani, M., Klein, K.: Shrinking the search space for clustered planarity. In: W.\u00a0Didimo, M.\u00a0Patrignani (eds.) GD\u00a0\u201912, LNCS, vol. 7704, pp. 90\u2013101. Springer (2012). https:\/\/doi.org\/10.1007\/978-3-642-36763-2_9","DOI":"10.1007\/978-3-642-36763-2_9"},{"issue":"2","key":"839_CR27","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/j.jda.2005.06.002","volume":"4","author":"S Cornelsen","year":"2006","unstructured":"Cornelsen, S., Wagner, D.: Completely connected clustered graphs. J. Discrete Algorithms 4(2), 313\u2013323 (2006). https:\/\/doi.org\/10.1016\/j.jda.2005.06.002","journal-title":"J. Discrete Algorithms"},{"key":"839_CR28","doi-asserted-by":"publisher","unstructured":"Cortese, P.F., Di Battista, G.: Clustered planarity. In: J.S.B. Mitchell, G.\u00a0Rote (eds.) SoCG\u00a0\u201905, pp. 32\u201334. ACM (2005). https:\/\/doi.org\/10.1145\/1064092.1064093","DOI":"10.1145\/1064092.1064093"},{"issue":"2","key":"839_CR29","doi-asserted-by":"publisher","first-page":"225","DOI":"10.7155\/jgaa.00165","volume":"12","author":"PF Cortese","year":"2008","unstructured":"Cortese, P.F., Di Battista, G., Frati, F., Patrignani, M., Pizzonia, M.: C-planarity of c-connected clustered graphs. J. Graph Algorithms Appl. 12(2), 225\u2013262 (2008)","journal-title":"J. Graph Algorithms Appl."},{"issue":"7","key":"839_CR30","doi-asserted-by":"publisher","first-page":"1856","DOI":"10.1016\/j.disc.2007.12.090","volume":"309","author":"PF Cortese","year":"2009","unstructured":"Cortese, P.F., Di Battista, G., Patrignani, M., Pizzonia, M.: On embedding a cycle in a plane graph. Discret. Math. 309(7), 1856\u20131869 (2009). https:\/\/doi.org\/10.1016\/j.disc.2007.12.090","journal-title":"Discret. Math."},{"key":"839_CR31","doi-asserted-by":"publisher","unstructured":"Cortese, P.F., Patrignani, M.: Clustered planarity = flat clustered planarity. In: T.C. Biedl, A.\u00a0Kerren (eds.) GD 2018, LNCS, vol. 11282, pp. 23\u201338. Springer (2018). https:\/\/doi.org\/10.1145\/1064092.1064093","DOI":"10.1145\/1064092.1064093"},{"key":"839_CR32","doi-asserted-by":"publisher","unstructured":"Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. Comput. Syst. Sci. 46(2), 218\u2013270 (1993). https:\/\/doi.org\/10.1007\/978-3-030-04414-5_2","DOI":"10.1007\/978-3-030-04414-5_2"},{"issue":"2","key":"839_CR33","doi-asserted-by":"publisher","first-page":"139","DOI":"10.7155\/jgaa.00461","volume":"22","author":"G Da Lozzo","year":"2018","unstructured":"Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M.: Computing nodetrix representations of clustered graphs. J. Graph Algorithms Appl. 22(2), 139\u2013176 (2018). https:\/\/doi.org\/10.7155\/jgaa.00461","journal-title":"J. Graph Algorithms Appl."},{"key":"839_CR34","doi-asserted-by":"publisher","unstructured":"Da Lozzo, G., Eppstein, D., Goodrich, M.T., Gupta, S.: Subexponential-time and FPT algorithms for embedded flat clustered planarity. In: A.\u00a0Brandst\u00e4dt, E.\u00a0K\u00f6hler, K.\u00a0Meer (eds.) WG 2018, LNCS, vol. 11159, pp. 111\u2013124. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-030-00256-5_10","DOI":"10.1007\/978-3-030-00256-5_10"},{"key":"839_CR35","doi-asserted-by":"publisher","unstructured":"Da Lozzo, G., Eppstein, D., Goodrich, M.T., Gupta, S.: C-planarity testing of embedded clustered graphs with bounded dual carving-width. In: B.M.P. Jansen, J.A. Telle (eds.) 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, September 11\u201313, 2019, Munich, Germany, LIPIcs, vol. 148, pp. 9:1\u20139:17. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2019.9","DOI":"10.4230\/LIPIcs.IPEC.2019.9"},{"key":"839_CR36","doi-asserted-by":"publisher","unstructured":"Dahlhaus, E.: A linear time algorithm to recognize clustered graphs and its parallelization. In: C.L. Lucchesi, A.V. Moura (eds.) LATIN\u00a0\u201998, LNCS, vol. 1380, pp. 239\u2013248. Springer (1998). https:\/\/doi.org\/10.1007\/BFb0054325","DOI":"10.1007\/BFb0054325"},{"key":"839_CR37","first-page":"571","volume-title":"Handbook on Graph Drawing and Visualization","author":"G Di Battista","year":"2013","unstructured":"Di Battista, G., Didimo, W.: Gdtoolkit. In: Tamassia, R. (ed.) Handbook on Graph Drawing and Visualization, pp. 571\u2013597. Chapman and Hall\/CRC, London (2013)"},{"key":"839_CR38","doi-asserted-by":"publisher","unstructured":"Di Battista, G., Didimo, W., Marcandalli, A.: Planarization of clustered graphs. In: P.\u00a0Mutzel, M.\u00a0J\u00fcnger, S.\u00a0Leipert (eds.) GD\u00a0\u201901, LNCS, vol. 2265, pp. 60\u201374. Springer (2001). https:\/\/doi.org\/10.1007\/3-540-45848-4_5","DOI":"10.1007\/3-540-45848-4_5"},{"issue":"3","key":"839_CR39","doi-asserted-by":"publisher","first-page":"349","DOI":"10.7155\/jgaa.00191","volume":"13","author":"G Di Battista","year":"2009","unstructured":"Di Battista, G., Frati, F.: Efficient c-planarity testing for embedded flat clustered graphs with small faces. J. Graph Algorithms Appl. 13(3), 349\u2013378 (2009)","journal-title":"J. Graph Algorithms Appl."},{"issue":"3","key":"839_CR40","doi-asserted-by":"publisher","first-page":"267","DOI":"10.7155\/jgaa.00167","volume":"12","author":"W Didimo","year":"2008","unstructured":"Didimo, W., Giordano, F., Liotta, G.: Overlapping cluster planarity. J. Graph Algorithms Appl. 12(3), 267\u2013291 (2008)","journal-title":"J. Graph Algorithms Appl."},{"key":"839_CR41","doi-asserted-by":"publisher","unstructured":"Feng, Q., Cohen, R.F., Eades, P.: Planarity for clustered graphs. In: P.G. Spirakis (ed.) ESA\u201995, LNCS, vol. 979, pp. 213\u2013226. Springer (1995). https:\/\/doi.org\/10.1007\/3-540-60313-1_145","DOI":"10.1007\/3-540-60313-1_145"},{"key":"839_CR42","doi-asserted-by":"publisher","unstructured":"Forster, M., Bachmaier, C.: Clustered level planarity. In: P.\u00a0van Emde\u00a0Boas, J.\u00a0Pokorn\u00fd, M.\u00a0Bielikov\u00e1, J.\u00a0Stuller (eds.) SOFSEM\u00a0\u201904, LNCS, vol. 2932, pp. 218\u2013228. Springer (2004). https:\/\/doi.org\/10.1007\/978-3-540-24618-3_18","DOI":"10.1007\/978-3-540-24618-3_18"},{"key":"839_CR43","doi-asserted-by":"publisher","unstructured":"Fulek, R., Kyncl, J.: Hanani-tutte for approximating maps of graphs. In: B.\u00a0Speckmann, C.D. T\u00f3th (eds.) SoCG\u00a0\u201918, LIPIcs, vol.\u00a099, pp. 39:1\u201339:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2018.39","DOI":"10.4230\/LIPIcs.SoCG.2018.39"},{"key":"839_CR44","unstructured":"Fulek, R., Kyncl, J., Malinovic, I., P\u00e1lv\u00f6lgyi, D.: Efficient c-planarity testing algebraically. CoRR abs\/1305.4519 (2013). arXiv:1305.4519"},{"issue":"4","key":"839_CR45","doi-asserted-by":"publisher","first-page":"P4.24","DOI":"10.37236\/5002","volume":"22","author":"R Fulek","year":"2015","unstructured":"Fulek, R., Kyncl, J., Malinovic, I., P\u00e1lv\u00f6lgyi, D.: Clustered planarity testing revisited. Electr. J. Comb. 22(4), P4.24 (2015)","journal-title":"Electr. J. Comb."},{"key":"839_CR46","doi-asserted-by":"crossref","unstructured":"Fulek, R., T\u00f3th, C.D.: Atomic embeddability, clustered planarity, and thickenability. CoRR abs\/1907.13086 (2019). arXiv:1907.13086","DOI":"10.1137\/1.9781611975994.175"},{"key":"839_CR47","doi-asserted-by":"publisher","unstructured":"Fulek, R., T\u00f3th, C.D.: Atomic embeddability, clustered planarity, and thickenability. In: S.\u00a0Chawla (ed.) Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5\u20138, 2020, pp. 2876\u20132895. SIAM (2020). https:\/\/doi.org\/10.1137\/1.9781611975994.175","DOI":"10.1137\/1.9781611975994.175"},{"key":"839_CR48","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0163-9","volume-title":"Algebraic Graph Theory. Graduate texts in Mathematics","author":"CD Godsil","year":"2001","unstructured":"Godsil, C.D., Royle, G.F.: Algebraic Graph Theory. Graduate texts in Mathematics. Springer, Berlin (2001). https:\/\/doi.org\/10.1007\/978-1-4613-0163-9"},{"key":"839_CR49","doi-asserted-by":"publisher","unstructured":"Goodrich, M.T., Lueker, G.S., Sun, J.Z.: C-planarity of extrovert clustered graphs. In: P.\u00a0Healy, N.S. Nikolov (eds.) GD \u201905, LNCS, vol. 3843, pp. 211\u2013222. Springer (2005). https:\/\/doi.org\/10.1007\/11618058_20","DOI":"10.1007\/11618058_20"},{"key":"839_CR50","doi-asserted-by":"publisher","DOI":"10.1002\/9781118159743","volume-title":"Fibonacci and Catalan Numbers: An Introduction","author":"R Grimaldi","year":"2012","unstructured":"Grimaldi, R.: Fibonacci and Catalan Numbers: An Introduction. Wiley, London (2012)"},{"issue":"3","key":"839_CR51","doi-asserted-by":"publisher","first-page":"30:1","DOI":"10.1145\/1367064.1367070","volume":"4","author":"Q Gu","year":"2008","unstructured":"Gu, Q., Tamaki, H.: Optimal branch-decomposition of planar graphs in O$(n^3)$ time. ACM Trans. Algorithms 4(3), 30:1-30:13 (2008). https:\/\/doi.org\/10.1145\/1367064.1367070","journal-title":"ACM Trans. Algorithms"},{"key":"839_CR52","doi-asserted-by":"publisher","unstructured":"Gutwenger, C., J\u00fcnger, M., Leipert, S., Mutzel, P., Percan, M., Weiskircher, R.: Advances in c-planarity testing of clustered graphs. In: S.G. Kobourov, M.T. Goodrich (eds.) GD \u201902, LNCS, vol. 2528, pp. 220\u2013235. Springer (2002). https:\/\/doi.org\/10.1007\/3-540-36151-0_21","DOI":"10.1007\/3-540-36151-0_21"},{"key":"839_CR53","doi-asserted-by":"publisher","unstructured":"Gutwenger, C., Mutzel, P., Schaefer, M.: Practical experience with hanani-tutte for testing c-planarity. In: C.C. McGeoch, U.\u00a0Meyer (eds.) ALENEX\u00a0\u201914, pp. 86\u201397. SIAM (2014). https:\/\/doi.org\/10.1137\/1.9781611973198.9","DOI":"10.1137\/1.9781611973198.9"},{"issue":"3","key":"839_CR54","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1016\/j.jda.2009.05.003","volume":"8","author":"S Hong","year":"2010","unstructured":"Hong, S., Nagamochi, H.: Convex drawings of hierarchical planar graphs and clustered planar graphs. J. Discrete Algorithms 8(3), 282\u2013295 (2010). https:\/\/doi.org\/10.1016\/j.jda.2009.05.003","journal-title":"J. Discrete Algorithms"},{"key":"839_CR55","unstructured":"Hong, S.H., Nagamochi, H.: Simpler algorithms for testing two-page book embedding of partitioned graphs. Theoretical Computer Science (2016)"},{"issue":"6","key":"839_CR56","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1145\/362248.362272","volume":"16","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Efficient algorithms for graph manipulation [H] (algorithm 447). Commun. ACM 16(6), 372\u2013378 (1973). https:\/\/doi.org\/10.1145\/362248.362272","journal-title":"Commun. ACM"},{"key":"839_CR57","doi-asserted-by":"publisher","unstructured":"Jel\u00ednek, V., Jel\u00ednkov\u00e1, E., Kratochv\u00edl, J., Lidick\u00fd, B.: Clustered planarity: embedded clustered graphs with two-component clusters. In: I.G. Tollis, M.\u00a0Patrignani (eds.) GD \u201908, LNCS, vol. 5417, pp. 121\u2013132. Springer (2008). https:\/\/doi.org\/10.1007\/978-3-642-00219-9_13","DOI":"10.1007\/978-3-642-00219-9_13"},{"issue":"3","key":"839_CR58","doi-asserted-by":"publisher","first-page":"379","DOI":"10.7155\/jgaa.00192","volume":"13","author":"E Jel\u00ednkov\u00e1","year":"2009","unstructured":"Jel\u00ednkov\u00e1, E., K\u00e1ra, J., Kratochv\u00edl, J., Pergel, M., Such\u00fd, O., Vyskocil, T.: Clustered planarity: small clusters in cycles and Eulerian graphs. J. Graph Algorithms Appl. 13(3), 379\u2013422 (2009)","journal-title":"J. Graph Algorithms Appl."},{"issue":"3","key":"839_CR59","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1002\/jgt.3190110306","volume":"11","author":"DS Johnson","year":"1987","unstructured":"Johnson, D.S., Pollak, H.O.: Hypergraph planarity and the complexity of drawing venn diagrams. J. Graph Theory 11(3), 309\u2013325 (1987). https:\/\/doi.org\/10.1002\/jgt.3190110306","journal-title":"J. Graph Theory"},{"issue":"1","key":"839_CR60","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/99902.99903","volume":"10","author":"T Kamada","year":"1991","unstructured":"Kamada, T., Kawai, S.: A general framework for visualizing abstract objects and relations. ACM Trans. Graph. 10(1), 1\u201339 (1991). https:\/\/doi.org\/10.1145\/99902.99903","journal-title":"ACM Trans. Graph."},{"key":"839_CR61","doi-asserted-by":"publisher","unstructured":"Kaufmann, M., van Kreveld, M.J., Speckmann, B.: Subdivision drawings of hypergraphs. In: I.G. Tollis, M.\u00a0Patrignani (eds.) Graph Drawing, 16th International Symposium, GD 2008, Heraklion, Crete, Greece, September 21\u201324, 2008. Revised Papers, Lecture Notes in Computer Science, vol. 5417, pp. 396\u2013407. Springer (2008). https:\/\/doi.org\/10.1007\/978-3-642-00219-9_39","DOI":"10.1007\/978-3-642-00219-9_39"},{"issue":"9","key":"839_CR62","doi-asserted-by":"publisher","first-page":"1155","DOI":"10.1016\/j.dam.2006.04.044","volume":"155","author":"H Nagamochi","year":"2007","unstructured":"Nagamochi, H., Kuroya, K.: Drawing c-planar biconnected clustered graphs. Discret. Appl. Math. 155(9), 1155\u20131174 (2007). https:\/\/doi.org\/10.1016\/j.dam.2006.04.044","journal-title":"Discret. Appl. Math."},{"key":"839_CR63","unstructured":"Niggemann, O.: Visual data mining of graph based data. Ph.D. thesis, University of Paderborn, Germany (2001). http:\/\/ubdata.uni-paderborn.de\/ediss\/17\/2001\/niggeman\/disserta.pdf"},{"issue":"4","key":"839_CR64","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S Oum","year":"2006","unstructured":"Oum, S., Seymour, P.D.: Approximating clique-width and branch-width. J. Comb. Theory Ser. B 96(4), 514\u2013528 (2006). https:\/\/doi.org\/10.1016\/j.jctb.2005.10.006","journal-title":"J. Comb. Theory Ser. B"},{"key":"839_CR65","doi-asserted-by":"publisher","unstructured":"Paiva, R., Rodrigues, G.N., Bonif\u00e1cio, R., Ladeira, M.: Exploring the combination of software visualization and data clustering in the software architecture recovery process. In: S.\u00a0Ossowski (ed.) Proceedings of the 31st Annual ACM Symposium on Applied Computing, Pisa, Italy, April 4\u20138, 2016, pp. 1309\u20131314. ACM (2016). https:\/\/doi.org\/10.1145\/2851613.2851765","DOI":"10.1145\/2851613.2851765"},{"issue":"2","key":"839_CR66","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N Robertson","year":"1991","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. X. Obstructions to tree-decomposition. J. Comb. Theory. Ser. B 52(2), 153\u2013190 (1991). https:\/\/doi.org\/10.1016\/0095-8956(91)90061-N","journal-title":"J. Comb. Theory. Ser. B"},{"issue":"2","key":"839_CR67","doi-asserted-by":"publisher","first-page":"8:1","DOI":"10.1145\/2556952","volume":"10","author":"J Ru\u00e9","year":"2014","unstructured":"Ru\u00e9, J., Sau, I., Thilikos, D.M.: Dynamic programming for graphs on surfaces. ACM Trans. Algorithms 10(2), 8:1-8:26 (2014). https:\/\/doi.org\/10.1145\/2556952","journal-title":"ACM Trans. Algorithms"},{"key":"839_CR68","unstructured":"Sas\u00e1k, R.: Comparing 17 graph parameters. Master\u2019s thesis, Department of Informatics, University of Bergen, Bergen, Norway (2010)"},{"issue":"4","key":"839_CR69","doi-asserted-by":"publisher","first-page":"367","DOI":"10.7155\/jgaa.00298","volume":"17","author":"M Schaefer","year":"2013","unstructured":"Schaefer, M.: Toward a theory of planarity: hanani\u2013tutte and planarity variants. J. Graph Algorithms Appl. 17(4), 367\u2013440 (2013). https:\/\/doi.org\/10.7155\/jgaa.00298","journal-title":"J. Graph Algorithms Appl."},{"issue":"2","key":"839_CR70","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"PD Seymour","year":"1994","unstructured":"Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica 14(2), 217\u2013241 (1994). https:\/\/doi.org\/10.1007\/BF01215352","journal-title":"Combinatorica"},{"key":"839_CR71","doi-asserted-by":"publisher","unstructured":"Thilikos, D.M., Serna, M.J., Bodlaender, H.L.: Constructive linear time algorithms for small cutwidth and carving-width. In: D.T. Lee, S.\u00a0Teng (eds.) ISAAC\u00a0\u201900, LNCS, vol. 1969, pp. 192\u2013203. Springer (2000). https:\/\/doi.org\/10.1007\/3-540-40996-3_17","DOI":"10.1007\/3-540-40996-3_17"},{"key":"839_CR72","doi-asserted-by":"publisher","unstructured":"van Bevern, R., Kanj, I.A., Komusiewicz, C., Niedermeier, R., Sorge, M.: Twins in subdivision drawings of hypergraphs. In: Y.\u00a0Hu, M.\u00a0N\u00f6llenburg (eds.) Graph Drawing and Network Visualization\u201424th International Symposium, GD 2016, Athens, Greece, September 19\u201321, 2016, Revised Selected Papers, Lecture Notes in Computer Science, vol. 9801, pp. 67\u201380. Springer (2016). https:\/\/doi.org\/10.1007\/978-3-319-50106-2_6","DOI":"10.1007\/978-3-319-50106-2_6"},{"key":"839_CR73","doi-asserted-by":"publisher","unstructured":"Vial, J.J.B., Da Lozzo, G., Goodrich, M.T.: Computing k-modal embeddings of planar digraphs. In: M.A. Bender, O.\u00a0Svensson, G.\u00a0Herman (eds.) ESA 2019, LIPIcs, vol. 144, pp. 17:1\u201317:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.17","DOI":"10.4230\/LIPIcs.ESA.2019.17"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00839-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00839-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00839-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,22]],"date-time":"2021-07-22T14:04:20Z","timestamp":1626962660000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00839-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,8]]},"references-count":73,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["839"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00839-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,8]]},"assertion":[{"value":"2 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}