[{"isi":1,"quality_controlled":"1","main_file_link":[{"url":"https://arxiv.org/abs/1602.01346","open_access":"1"}],"external_id":{"isi":[]},"oa":1,"language":[{}],"month":"12","department":[{"_id":"UlWa","tree":[{"_id":"ResearchGroups"},{"_id":"IST"}]}],"publication_status":"published","acknowledgement":"I would like to thank Jan Kynčl, Dömötör Pálvölgyi and anonymous referees for many comments and suggestions that helped to improve the presentation of the result.","volume":66,"date_updated":"2023-09-27T12:14:49Z","dini_type":"doc-type:article","date_created":"2018-12-11T11:48:32Z","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"1165"}]},"author":[{"orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","first_name":"Radoslav"}],"creator":{"login":"kschuh","id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87"},"publist_id":"6860","page":"1 - 13","citation":{"ista":"Fulek R. 2017. C-planarity of embedded cyclic c-graphs. Computational Geometry: Theory and Applications. 66, 1–13.","apa":"Fulek, R. (2017). C-planarity of embedded cyclic c-graphs. Computational Geometry: Theory and Applications. Elsevier. https://doi.org/10.1016/j.comgeo.2017.06.016","ieee":"R. Fulek, “C-planarity of embedded cyclic c-graphs,” Computational Geometry: Theory and Applications, vol. 66. Elsevier, pp. 1–13, 2017.","chicago":"Fulek, Radoslav. “C-Planarity of Embedded Cyclic c-Graphs.” Computational Geometry: Theory and Applications. Elsevier, 2017. https://doi.org/10.1016/j.comgeo.2017.06.016.","mla":"Fulek, Radoslav. “C-Planarity of Embedded Cyclic c-Graphs.” Computational Geometry: Theory and Applications, vol. 66, Elsevier, 2017, pp. 1–13, doi:10.1016/j.comgeo.2017.06.016.","short":"R. Fulek, Computational Geometry: Theory and Applications 66 (2017) 1–13."},"publication":"Computational Geometry: Theory and Applications","date_published":"2017-12-01T00:00:00Z","scopus_import":"1","dc":{"creator":["Fulek, Radoslav"],"description":["We show that c-planarity is solvable in quadratic time for flat clustered graphs with three clusters if the combinatorial embedding of the underlying graph is fixed. In simpler graph-theoretical terms our result can be viewed as follows. Given a graph G with the vertex set partitioned into three parts embedded on a 2-sphere, our algorithm decides if we can augment G by adding edges without creating an edge-crossing so that in the resulting spherical graph the vertices of each part induce a connected sub-graph. We proceed by a reduction to the problem of testing the existence of a perfect matching in planar bipartite graphs. We formulate our result in a slightly more general setting of cyclic clustered graphs, i.e., the simple graph obtained by contracting each cluster, where we disregard loops and multi-edges, is a cycle."],"identifier":["https://research-explorer.ista.ac.at/record/794"],"type":["info:eu-repo/semantics/article","doc-type:article","text","http://purl.org/coar/resource_type/c_6501"],"language":["eng"],"date":["2017"],"title":["C-planarity of embedded cyclic c-graphs"],"publisher":["Elsevier"],"relation":["info:eu-repo/semantics/altIdentifier/doi/10.1016/j.comgeo.2017.06.016","info:eu-repo/semantics/altIdentifier/wos/000412039700001"],"rights":["info:eu-repo/semantics/openAccess"],"source":["Fulek R. C-planarity of embedded cyclic c-graphs. Computational Geometry: Theory and Applications. 2017;66:1-13. doi:10.1016/j.comgeo.2017.06.016"]},"uri_base":"https://research-explorer.ista.ac.at","article_processing_charge":"No","day":"01","intvolume":" 66","status":"public","_id":"794","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","oa_version":"Preprint","type":"journal_article","abstract":[{"lang":"eng"}]}]