{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:18Z","timestamp":1740109278354,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2019,1,30]],"date-time":"2019-01-30T00:00:00Z","timestamp":1548806400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["Ka812\/17-1"],"award-info":[{"award-number":["Ka812\/17-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0? e della Ricerca","award":["PRIN 20157EFM5C"],"award-info":[{"award-number":["PRIN 20157EFM5C"]}]},{"DOI":"10.13039\/100010665","name":"H2020 Marie Sk\u0142odowska-Curie Actions","doi-asserted-by":"publisher","award":["734922"],"award-info":[{"award-number":["734922"]}],"id":[{"id":"10.13039\/100010665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0? e della Ricerca","doi-asserted-by":"publisher","award":["Joint Mobility Program 34120"],"award-info":[{"award-number":["Joint Mobility Program 34120"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Deutscher Akademischer Austauschdienst","award":["Joint Mobility Program 57397196"],"award-info":[{"award-number":["Joint Mobility Program 57397196"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,6]]},"DOI":"10.1007\/s00453-018-00541-w","type":"journal-article","created":{"date-parts":[[2019,1,31]],"date-time":"2019-01-31T06:01:45Z","timestamp":1548914505000},"page":"2484-2526","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Clustered Planarity with Pipes"],"prefix":"10.1007","volume":"81","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7602-1524","authenticated-orcid":false,"given":"Patrizio","family":"Angelini","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2396-5174","authenticated-orcid":false,"given":"Giordano","family":"Da Lozzo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,1,30]]},"reference":[{"key":"541_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-05412-3","volume-title":"Proofs from THE BOOK","author":"M Aigner","year":"2004","unstructured":"Aigner, M., Ziegler, G.M.: Proofs from THE BOOK, 3rd edn. Springer, Berlin (2004)","edition":"3"},{"key":"541_CR2","doi-asserted-by":"publisher","unstructured":"Akitaya, H.A., Fulek, R., T\u00f3th, C.D.: Recognizing weak embeddings of graphs. In: Czumaj, A. (ed.) Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, 7\u201310 Jan 2018, pp. 274\u2013292. SIAM (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.20","DOI":"10.1137\/1.9781611975031.20"},{"key":"541_CR3","doi-asserted-by":"publisher","unstructured":"Angelini, P., Da Lozzo, G.: Clustered planarity with pipes. In: Hong, S.-H. (ed.) 27th International Symposium on Algorithms and Computation, ISAAC 2016, 12\u201314 Dec 2016, Sydney, Australia. LIPIcs, vol. 64, pp. 13:1\u201313:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2016.13","DOI":"10.4230\/LIPIcs.ISAAC.2016.13"},{"issue":"4","key":"541_CR4","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)","journal-title":"Algorithmica"},{"key":"541_CR5","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.tcs.2014.11.016","volume":"575","author":"P Angelini","year":"2015","unstructured":"Angelini, P., Da Lozzo, G., Neuwirth, D.: Advancements on SEFE and partitioned book embedding problems. Theor. Comput. Sci. 575, 71\u201389 (2015)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"541_CR6","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1137\/S0097539794279626","volume":"27","author":"P Bertolazzi","year":"1998","unstructured":"Bertolazzi, P., Di Battista, G., Mannino, C., Tamassia, R.: Optimal upward planarity testing of single-source digraphs. SIAM J. Comput. 27(1), 132\u2013169 (1998)","journal-title":"SIAM J. Comput."},{"key":"541_CR7","volume-title":"Handbook of Graph Drawing and Visualization","author":"T Bl\u00e4sius","year":"2013","unstructured":"Bl\u00e4sius, T., Kobourov, S.G., Rutter, I.: Simultaneous embedding of planar graphs. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization. CRC Press, Boca Raton (2013)"},{"key":"541_CR8","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)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"541_CR9","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1145\/2738054","volume":"12","author":"T Bl\u00e4sius","year":"2016","unstructured":"Bl\u00e4sius, T., Rutter, I.: Simultaneous PQ-ordering with applications to constrained embedding problems. ACM Trans. Algorithms 12(2), 16 (2016)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"541_CR10","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. J. Comput. Syst. Sci. 13(3), 335\u2013379 (1976). https:\/\/doi.org\/10.1016\/S0022-0000(76)80045-1","journal-title":"J. Comput. Syst. Sci."},{"key":"541_CR11","doi-asserted-by":"crossref","unstructured":"Chang, H.-C., Erickson, J., Xu, C.: Detecting weakly simple polygons. In: Indyk, P. (ed.) Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pp. 1655\u20131670. SIAM (2015)","DOI":"10.1137\/1.9781611973730.110"},{"key":"541_CR12","doi-asserted-by":"publisher","unstructured":"Chimani, M., Klein, K.: Shrinking the search space for clustered planarity. In: Didimo, W., Patrignani, M. (eds.) Graph Drawing\u201420th International Symposium, GD 2012, Redmond, WA, USA, 19\u201321 Sept 2012. Revised Selected Papers, Lecture Notes in Computer Science, 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":"541_CR13","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":"3","key":"541_CR14","doi-asserted-by":"publisher","first-page":"391","DOI":"10.7155\/jgaa.00115","volume":"9","author":"PF Cortese","year":"2005","unstructured":"Cortese, P.F., Di Battista, G., Patrignani, M., Pizzonia, M.: Clustering cycles into cycles of clusters. J. Graph Algorithms Appl. 9(3), 391\u2013413 (2005)","journal-title":"J. Graph Algorithms Appl."},{"issue":"7","key":"541_CR15","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. Discrete Math. 309(7), 1856\u20131869 (2009)","journal-title":"Discrete Math."},{"key":"541_CR16","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: Brandst\u00e4dt, A., K\u00f6hler, E., Meer, K. (eds.) Graph-Theoretic Concepts in Computer Science\u201444th International Workshop, WG 2018, Cottbus, Germany, 27\u201329 June 2018, Proceedings. Lecture Notes in Computer Science, 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":"541_CR17","doi-asserted-by":"crossref","unstructured":"Feng, Q.-W., Cohen, R.F., Eades, P.: Planarity for clustered graphs. In: Spirakis, P.G. (ed.) Third Annual European Symposium on Algorithms\u2014ESA \u201995. LNCS, vol. 979, pp. 213\u2013226. Springer (1995)","DOI":"10.1007\/3-540-60313-1_145"},{"key":"541_CR18","doi-asserted-by":"crossref","unstructured":"Fulek, R.: Toward the Hanani\u2013Tutte theorem for clustered graphs. arXiv:1410.3022 (2014)","DOI":"10.1007\/978-3-319-12340-0_15"},{"key":"541_CR19","doi-asserted-by":"crossref","unstructured":"Fulek, R.: Towards the Hanani\u2013Tutte theorem for clustered graphs. In: Kratsch, D., Todinca, I. (eds.) 40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014. LNCS, vol. 8747, pp. 176\u2013188. Springer (2014)","DOI":"10.1007\/978-3-319-12340-0_15"},{"key":"541_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.comgeo.2017.06.016","volume":"66","author":"R Fulek","year":"2017","unstructured":"Fulek, R.: C-planarity of embedded cyclic c-graphs. Comput. Geom. 66, 1\u201313 (2017). https:\/\/doi.org\/10.1016\/j.comgeo.2017.06.016","journal-title":"Comput. Geom."},{"key":"541_CR21","doi-asserted-by":"publisher","unstructured":"Fulek, R.: Embedding graphs into embedded graphs. In: Okamoto, Y., Tokuyama, T. (eds.) 28th International Symposium on Algorithms and Computation, ISAAC 2017, 9\u201312 Dec 2017, Phuket, Thailand. LIPIcs, vol.\u00a092, pp. 34:1\u201334:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2017.34","DOI":"10.4230\/LIPIcs.ISAAC.2017.34"},{"key":"541_CR22","doi-asserted-by":"publisher","unstructured":"Fulek, R., Kyncl, J.: Hanani\u2013Tutte for approximating maps of graphs. In: Speckmann, B., T\u00f3th, C.D. (eds.) 34th International Symposium on Computational Geometry, SoCG 2018, 11\u201314 June 2018, Budapest, Hungary. 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"},{"issue":"1","key":"541_CR23","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0304-3975(02)00435-8","volume":"296","author":"W-L Hsu","year":"2003","unstructured":"Hsu, W.-L., McConnell, R.M.: PC trees and circular-ones arrangements. Theor. Comput. Sci. 296(1), 99\u2013116 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"541_CR24","volume-title":"Handbook of Data Structures and Applications","author":"W-L Hsu","year":"2004","unstructured":"Hsu, W.-L., McConnell, R.M.: PQ trees, PC trees, and planar graphs. In: Mehta, D.P., Sahni, S. (eds.) Handbook of Data Structures and Applications. Chapman and Hall, London (2004)"},{"key":"541_CR25","doi-asserted-by":"crossref","unstructured":"Jel\u00ednek, V., Jel\u00ednkov\u00e1, E., Kratochv\u00edl, J., Lidick\u00fd, B.: Clustered planarity: embedded clustered graphs with two-component clusters. In: Tollis, I.G., Patrignani, M. (eds.) 16th International Symposium on Graph Drawing, GD 2008. LNCS, vol. 5417, pp. 121\u2013132. Springer (2008)","DOI":"10.1007\/978-3-642-00219-9_13"},{"issue":"2","key":"541_CR26","doi-asserted-by":"publisher","first-page":"205","DOI":"10.7155\/jgaa.00184","volume":"13","author":"M J\u00fcnger","year":"2009","unstructured":"J\u00fcnger, M., Schulz, M.: Intersection graphs in simultaneous embedding with fixed edges. J. Graph Algorithms Appl. 13(2), 205\u2013218 (2009)","journal-title":"J. Graph Algorithms Appl."},{"issue":"4","key":"541_CR27","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)","journal-title":"J. Graph Algorithms Appl."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-00541-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-00541-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-00541-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,25]],"date-time":"2020-11-25T19:41:31Z","timestamp":1606333291000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-00541-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,30]]},"references-count":27,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["541"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-00541-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,1,30]]},"assertion":[{"value":"6 June 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 December 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}