C-planarity of embedded cyclic c-graphs

R. Fulek, Computational Geometry: Theory and Applications 66 (2017) 1–13.


Journal Article | Published | English
Department
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.
Publishing Year
Date Published
2017-12-01
Journal Title
Computational Geometry: Theory and Applications
Acknowledgement
I would like to thank Jan Kynčl, Dömötör Pálvölgyi and anonymous referees for many comments and suggestions that helped to improve the presentation of the result.
Volume
66
Page
1 - 13
IST-REx-ID

Cite this

Fulek R. C-planarity of embedded cyclic c-graphs. Computational Geometry: Theory and Applications. 2017;66:1-13. doi:10.1016/j.comgeo.2017.06.016
Fulek, R. (2017). C-planarity of embedded cyclic c-graphs. Computational Geometry: Theory and Applications, 66, 1–13. https://doi.org/10.1016/j.comgeo.2017.06.016
Fulek, Radoslav. “C-Planarity of Embedded Cyclic c-Graphs.” Computational Geometry: Theory and Applications 66 (2017): 1–13. https://doi.org/10.1016/j.comgeo.2017.06.016.
R. Fulek, “C-planarity of embedded cyclic c-graphs,” Computational Geometry: Theory and Applications, vol. 66, pp. 1–13, 2017.
Fulek R. 2017. C-planarity of embedded cyclic c-graphs. Computational Geometry: Theory and Applications. 66, 1–13.
Fulek, Radoslav. “C-Planarity of Embedded Cyclic c-Graphs.” Computational Geometry: Theory and Applications, vol. 66, Elsevier, 2017, pp. 1–13, doi:10.1016/j.comgeo.2017.06.016.

Link(s) to Main File(s)
Access Level
OA Open Access
Material in IST:
Earlier Version

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar