---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Radoslav
foaf_name: Fulek, Radoslav
foaf_surname: Fulek
foaf_workInfoHomepage: http://www.librecat.org/personId=39F3FFE4-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0001-8485-1774
bibo_doi: 10.1016/j.comgeo.2017.06.016
bibo_volume: 66
dct_date: 2017^xs_gYear
dct_language: eng
dct_publisher: Elsevier@
dct_title: C-planarity of embedded cyclic c-graphs@
...