C-Planarity of C-Connected Clustered Graphs

Abstract

We present the first characterization of c-planarity for c-connected clustered graphs. The characterization is based on the interplay between the hierarchy of the clusters and the hierarchies of the triconnected and biconnected components of the underlying graph. Based on such a characterization, we provide a linear-time c-planarity testing and embedding algorithm for c-connected clustered graphs. The algorithm is reasonably easy to implement, since it exploits as building blocks simple algorithmic tools like the computation of lowest common ancestors, minimum and maximum spanning trees, and counting sorts. It also makes use of well-known data structures as SPQR-trees and BC-trees. If the test fails, the algorithm identifies a structural element responsible for the non-c-planarity of the input clustered graph.