|
Description: |
> |
The complexity status of c-planarity testing is
unknown. It has been shown by Eades, Feng and
Dahlhaus that c-planarity can be tested in
linear time for c-connected graphs, i.e., graphs
in which the cluster induced subgraphs are
connected.
In this project we study the complexity status of c-planarity testing
for general clustered graphs. The idea is to use the known c-planarity
testing algorithms for c-connected clustered graphs. For this, a
general clustered graph has to be augmented to make it
c-connected. Unfortunately, the complexity status of this problem is
also unknown. What makes the problem difficult is that we have to deal
with all embeddings of the given clustered graph.
Our first goal towards general c-planarity
testing is the planar connectivity augmentation using SPQR-trees
with linear running time: given a planar graph G and a subset W of
its vertices, introduce a minimum cardinality edge set to the subgraph
induced by W to get the subgraph connected. G is still planar
after augmentation. We apply this technique for a subclass of
non-c-connected clustered graphs, and solve the problem of
c-planarity testing in polynomial time for special cases. In
further work, we will study the complexity status of the general
problems.
As a by-product, we have constructed a triangulation for c-planar
embedded clustered graphs that runs in linear time and have given a
criterion how to augment c-planar embedded clustered graphs. |
|
