C-Planarity of C-Connected Clustered Graphs - Cortese, Pier Francesco; Di Battista, Giuseppe; Frati, Fabrizio; Patrignani, Maurizio; Pizzonia, Maurizio (Journal of Graph Algorithms and Applications, 2008)
We present the first characterization of c-planarity forc-connected clustered graphs. The characterization is based on theinterplay between the hierarchy of the clusters and the hierarchies ofthe triconnected and biconnected components of the underlying graph.Based on such a characterization, we provide alinear-time c-planarity testing and embedding algorithm forc-connected clustered graphs. The algorithm is reasonably easy toimplement, since it exploits as building blocks simple algorithmictools like the computation of lowest common ancestors, minimumand maximum spanning trees, and counting sorts. It also makes useof 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-planarityof the input clustered graph. <!---->