\(c\)-planarity of embedded cyclic \(c\)-graphs (Q1693313)

Testing planarity of graphs with additional constrains is a popular topic in graph visualizations. One of these planarity variant is \(c\)-planarity. The article proves 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. The result can be formulated in graph theoretical terms as follows: Given a graph \(G\) with the vertex set partitioned into three parts embedded on a 2-sphere, the algorithm decides if \(G\) can be augmented 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.