CPlanarity of Embedded Cyclic cGraphsFulek, Radoslav (2016) CPlanarity of Embedded Cyclic cGraphs. In: Graph Drawing and Network Visualization. GD 2016, September, 19.  21., 2016 , pp. 94106(Official URL: http://dx.doi.org/10.1007/9783319501062_8). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319501062_8
AbstractWe show that cplanarity is solvable in quadratic time for flat clustered graphs with three clusters if the combinatorial embedding of the underlying graph is fixed. In simpler graphtheoretical terms our result can be viewed as follows. Given a graph G with the vertex set partitioned into three parts embedded on a 2sphere, our algorithm decides if we can augment G by adding edges without creating an edgecrossing so that in the resulting spherical graph the vertices of each part induce a connected subgraph. 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 multiedges, is a cycle.
Actions (login required)
