A New Perspective on Clustered Planarity as a Combinatorial Embedding Problem - Graph Drawing - page 446

vertices (Theorem 2). Thus, to solve c-planarity for flat-clustered graphs, one needs to
solve an embedding problem on general planar multi-graphs that is so far only solved
on a set of parallel edges (with absolutely non-trivial algorithms). This indicates that we
are still far away from solving the c-planarity problem even for flat-clustered graphs.
Cortese et al. [9] give a linear-time algorithm for testing c-planarity of a flat-clustered
cycle (i.e., G is a simple cycle) if the skeleton of the cd-tree's root is a multi-cycle.
Requiring that G is a cycle implies that the skeleton of each non-root node in T has the
property that the blocks incident to the parent vertex are simple cycles. Thus, in terms
of constrained planarity, they show how to test planarity of multi-cycles with partition-
constraints where each partition has size two. The result can be extended to a special
case of c-planarity where the clustering is not flat. However, the cd-tree fails to have
easy-to-state properties in this case, which shows that the cd-tree perspective of course
has some limitations. Later, Cortese et al. [10] extended this result to the case where G
is still a cycle, while the skeleton of the root can be an arbitrary planar multi-graph that
has a fixed embeddingup to the ordering of parallel edges. This is equivalent to testing
planarity of such a graph with partition-constraints where each partition has size two.
Jelínková et al. [20] consider the case where each cluster contains at most three
vertices (with additional restrictions). Consider a cluster containing only two vertices
u and v .If u and v are connected, then the region representing the cluster can be always
added and we can omit the cluster. Otherwise, the region representing the cluster in
a c-planar drawing implies that one can add the edge uv to G , yielding an equivalent
instance. Thus, one can assume that every cluster has size exactly 3, which yields flat-
clustered graphs. In this setting they give efficient algorithms for the cases that G is a
cycle and G is 3-connected. Moreover, they give an FPT- a lgorithm for the case that G
is an Eulerian graph with k nodes, i.e., a graph obtained from a 3-connected graph of
size k by multiplying and then subdividing edges.
In case G is 3-connected, its planar embedding is fixed and thustheedge-ordering
of non-virtual vertices is fixed. Thus, one obtains partitioned full-constraints with the
restriction that there are only three partitions. Clearly, the requirement that G is 3-
connected also restricts the possible skeletons of the root of the cd-tree. It is an in-
teresting open question whether planarity with partitioned full-constraints with at most
three partitions can be tested efficiently for arbitrary planar graphs. In case G is a cy-
cle, one obtains partition constraints with only three partitions and each partition has
size two. Note that this in particular restricts the skeleton of the root to have maximum
degree 6. Although these kind of constraints seem pretty simple to handle, the algo-
rithm by Jelínková et al. is pretty involved. It seems like one barrier where constrained
embedding becomes difficult is when there are partition constraints with three or more
partitions (see also Theorem 4). The result aboutEulerian graphs in a sense combines
the cases where G is 3-connected and a cycle. A vertex has either degree two and thus
yields a partition of size two or it is one of the constantly many vertices with higher
degree for which the edge-ordering is partly fixed.

4.2 General Clustered Graphs

Expressing c-planarity for general clustered graphs (not necessarily flat) in terms of
constrained planarity problems is harder for the following reason. Consider a leaf μ in