C-Planarity of Embedded Cyclic c-Graphs

Fulek, Radoslav (2016) C-Planarity of Embedded Cyclic c-Graphs. In: Graph Drawing and Network Visualization. GD 2016, September, 19. - 21., 2016 , pp. 94-106(Official URL: http://dx.doi.org/10.1007/978-3-319-50106-2_8).

Full text not available from this repository.


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.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.350 Clusters
G Algorithms and Complexity > G.770 Planarity Testing
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1535

Actions (login required)

View Item View Item