C-planarity of embedded cyclic c-graphs
LNCS
Fulek, Radoslav
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.
Springer
2016
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
http://purl.org/coar/resource_type/c_5794
https://research-explorer.app.ist.ac.at/record/1165
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>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-319-50106-2_8
info:eu-repo/grantAgreement/EC/FP7/291734
info:eu-repo/semantics/openAccess