conference paper published yes Radoslav Fulek author 39F3FFE4-F248-11E8-B48F-1D18A9856A870000-0001-8485-1774 UlWa department GD: Graph Drawing and Network Visualization International IST Postdoc Fellowship Programme project 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. Springer2016Athens, Greece eng 1602.01346 00040547850000810.1007/978-3-319-50106-2_8 9801 94 - 106 https://research-explorer.ista.ac.at/record/794 Fulek, R. (2016). C-planarity of embedded cyclic c-graphs (Vol. 9801, pp. 94–106). Presented at the GD: Graph Drawing and Network Visualization, Athens, Greece: Springer. <a href="https://doi.org/10.1007/978-3-319-50106-2_8">https://doi.org/10.1007/978-3-319-50106-2_8</a> R. Fulek, “C-planarity of embedded cyclic c-graphs,” presented at the GD: Graph Drawing and Network Visualization, Athens, Greece, 2016, vol. 9801, pp. 94–106. R. Fulek, in:, Springer, 2016, pp. 94–106. Fulek R. 2016. C-planarity of embedded cyclic c-graphs. GD: Graph Drawing and Network Visualization, LNCS, vol. 9801, 94–106. Fulek, Radoslav. “C-Planarity of Embedded Cyclic c-Graphs,” 9801:94–106. Springer, 2016. <a href="https://doi.org/10.1007/978-3-319-50106-2_8">https://doi.org/10.1007/978-3-319-50106-2_8</a>. Fulek R. C-planarity of embedded cyclic c-graphs. In: Vol 9801. Springer; 2016:94-106. doi:<a href="https://doi.org/10.1007/978-3-319-50106-2_8">10.1007/978-3-319-50106-2_8</a> Fulek, Radoslav. <i>C-Planarity of Embedded Cyclic c-Graphs</i>. Vol. 9801, Springer, 2016, pp. 94–106, doi:<a href="https://doi.org/10.1007/978-3-319-50106-2_8">10.1007/978-3-319-50106-2_8</a>. 11652018-12-11T11:50:30Z2025-09-22T09:54:03Z