{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,6]],"date-time":"2025-08-06T13:26:17Z","timestamp":1754486777866,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030002558"},{"type":"electronic","value":"9783030002565"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-00256-5_10","type":"book-chapter","created":{"date-parts":[[2018,9,1]],"date-time":"2018-09-01T08:22:08Z","timestamp":1535790128000},"page":"111-124","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Subexponential-Time and FPT Algorithms for Embedded Flat Clustered Planarity"],"prefix":"10.1007","author":[{"given":"Giordano","family":"Da Lozzo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Eppstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael T.","family":"Goodrich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siddharth","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,9,2]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Akitaya, H.A., Fulek, R., T\u00f3th, C.D.: Recognizing weak embeddings of graphs. In: Czumaj, A. (ed.) SODA 2018, pp. 274\u2013292. SIAM (2018)","DOI":"10.1137\/1.9781611975031.20"},{"key":"10_CR2","unstructured":"Angelini, P., Da Lozzo, G.: Clustered planarity with pipes. In: Hong, S. (ed.) ISAAC 2016. LIPIcs, vol. 64, pp. 13:1\u201313:13. Schloss Dagstuhl - LZI (2016)"},{"issue":"4","key":"10_CR3","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"},{"issue":"2","key":"10_CR4","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)","journal-title":"Comput. Geom."},{"issue":"2","key":"10_CR5","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12(2), 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"key":"10_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/978-3-662-45803-7_18","volume-title":"Graph Drawing","author":"MJ Bannister","year":"2014","unstructured":"Bannister, M.J., Eppstein, D.: Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 210\u2013221. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-45803-7_18"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Biedl, T.: Drawing planar partitions III: two constrained embedding problems. Technical report RRR 13\u201398, Rutcor Research Report (1998)","DOI":"10.1145\/276884.276917"},{"key":"10_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."},{"key":"10_CR9","unstructured":"Borradaile, G., Erickson, J., Le, H., Weber, R.: Embedded-width: a variant of treewidth for plane graphs. CoRR abs\/1703.07532 (2017). http:\/\/arxiv.org\/abs\/1703.07532"},{"key":"10_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1007\/978-3-662-45803-7_35","volume-title":"Graph Drawing","author":"M Chimani","year":"2014","unstructured":"Chimani, M., Di Battista, G., Frati, F., Klein, K.: Advances on testing C-planarity of embedded flat clustered graphs. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 416\u2013427. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-45803-7_35"},{"key":"10_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-642-36763-2_9","volume-title":"Graph Drawing","author":"M Chimani","year":"2013","unstructured":"Chimani, M., Klein, K.: Shrinking the search space for clustered planarity. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 90\u2013101. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-36763-2_9"},{"issue":"2","key":"10_CR12","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)","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"10_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. JGAA 12(2), 225\u2013262 (2008)","journal-title":"JGAA"},{"issue":"1","key":"10_CR14","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"Da Lozzo, G., Eppstein, D., Goodrich, M.T., Gupta, S.: Subexponential-time and FPT algorithms for embedded flat clustered planarity. CoRR abs\/1803.05465 (2018). http:\/\/arxiv.org\/abs\/1803.05465","DOI":"10.1007\/978-3-030-00256-5_10"},{"key":"10_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/BFb0054325","volume-title":"LATIN\u201998: Theoretical Informatics","author":"E Dahlhaus","year":"1998","unstructured":"Dahlhaus, E.: A linear time algorithm to recognize clustered planar graphs and its parallelization. In: Lucchesi, C.L., Moura, A.V. (eds.) LATIN 1998. LNCS, vol. 1380, pp. 239\u2013248. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0054325"},{"issue":"3","key":"10_CR17","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. JGAA 13(3), 349\u2013378 (2009)","journal-title":"JGAA"},{"key":"10_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/3-540-60313-1_145","volume-title":"Algorithms \u2014 ESA \u201995","author":"Q-W Feng","year":"1995","unstructured":"Feng, Q.-W., Cohen, R.F., Eades, P.: Planarity for clustered graphs. In: Spirakis, P. (ed.) ESA 1995. LNCS, vol. 979, pp. 213\u2013226. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-60313-1_145"},{"key":"10_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/978-3-319-50106-2_8","volume-title":"Graph Drawing and Network Visualization","author":"R Fulek","year":"2016","unstructured":"Fulek, R.: C-planarity of embedded cyclic c-graphs. In: Hu, Y., N\u00f6llenburg, M. (eds.) GD 2016. LNCS, vol. 9801, pp. 94\u2013106. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-50106-2_8"},{"key":"10_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/11618058_20","volume-title":"Graph Drawing","author":"MT Goodrich","year":"2006","unstructured":"Goodrich, M.T., Lueker, G.S., Sun, J.Z.: C-planarity of extrovert clustered graphs. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 211\u2013222. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11618058_20"},{"key":"10_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/3-540-36151-0_21","volume-title":"Graph Drawing","author":"C Gutwenger","year":"2002","unstructured":"Gutwenger, C., J\u00fcnger, M., Leipert, S., Mutzel, P., Percan, M., Weiskircher, R.: Advances in C-planarity testing of clustered graphs. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol. 2528, pp. 220\u2013236. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-36151-0_21"},{"key":"10_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-642-00219-9_13","volume-title":"Graph Drawing","author":"V Jel\u00ednek","year":"2009","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.) GD 2008. LNCS, vol. 5417, pp. 121\u2013132. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-00219-9_13"},{"issue":"3","key":"10_CR23","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. JGAA 13(3), 379\u2013422 (2009)","journal-title":"JGAA"},{"issue":"3","key":"10_CR24","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0022-0000(86)90030-9","volume":"32","author":"GL Miller","year":"1986","unstructured":"Miller, G.L.: Finding small simple cycle separators for 2-connected planar graphs. J. Comput. Syst. Sci. 32(3), 265\u2013279 (1986)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-00256-5_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T13:24:56Z","timestamp":1710336296000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-00256-5_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030002558","9783030002565"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-00256-5_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"2 September 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Cottbus","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 June 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"44","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.wg2018.b-tu.de\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"66","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"45% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"11,5","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}