Portal de Periódicos da CAPES

C-Planarity of C-Connected Clustered Graphs

2008; Volume: 12; Issue: 2 Linguagem: Inglês

10.7155/jgaa.00165

1526-1719

Pier Francesco Cortese, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Maurizio Pizzonia,

Graph Theory and Algorithms

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-cplanarity of the input clustered graph.