@article{794,
abstract = {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.},
author = {Fulek, Radoslav},
journal = {Computational Geometry: Theory and Applications},
pages = {1 -- 13},
publisher = {Elsevier},
title = {{C-planarity of embedded cyclic c-graphs}},
doi = {10.1016/j.comgeo.2017.06.016},
volume = {66},
year = {2017},
}