C-planarity of embedded cyclic c-graphs Fulek, Radoslav ; https://orcid.org/0000-0001-8485-1774 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. Elsevier 2017 info:eu-repo/semantics/article doc-type:Article Article http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/794 Fulek R. C-planarity of embedded cyclic c-graphs. <i>Computational Geometry: Theory and Applications</i>. 2017;66:1-13. doi:<a href="https://doi.org/10.1016/j.comgeo.2017.06.016">10.1016/j.comgeo.2017.06.016</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1016/j.comgeo.2017.06.016 info:eu-repo/semantics/altIdentifier/wos/000412039700001 info:eu-repo/semantics/altIdentifier/arxiv/1602.01346 info:eu-repo/semantics/openAccess