Geodesic
C-Planarity of C-Connected Clustered Graphs
Journal of Graph Algorithms and Applications, Tome 12 (2008) no. 2, pp. 225-262.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00165
Keywords: graph drawing, clustered planarity, c-connected clustered graphs, linear-time algorithm, spqr-tree decomposition, bc-tree decomposition 
@article{JGAA_2008_12_2_a2,
     author = {Pier Francesco Cortese and Giuseppe Di Battista and Fabrizio Frati and Maurizio Patrignani and Maurizio Pizzonia},
     title = {C-Planarity of {C-Connected} {Clustered} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {225--262},
     publisher = {mathdoc},
     volume = {12},
     number = {2},
     year = {2008},
     doi = {10.7155/jgaa.00165},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00165/}
}
TY  - JOUR
AU  - Pier Francesco Cortese
AU  - Giuseppe Di Battista
AU  - Fabrizio Frati
AU  - Maurizio Patrignani
AU  - Maurizio Pizzonia
TI  - C-Planarity of C-Connected Clustered Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2008
SP  - 225
EP  - 262
VL  - 12
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00165/
DO  - 10.7155/jgaa.00165
LA  - en
ID  - JGAA_2008_12_2_a2
ER  - 
%0 Journal Article
%A Pier Francesco Cortese
%A Giuseppe Di Battista
%A Fabrizio Frati
%A Maurizio Patrignani
%A Maurizio Pizzonia
%T C-Planarity of C-Connected Clustered Graphs
%J Journal of Graph Algorithms and Applications
%D 2008
%P 225-262
%V 12
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00165/
%R 10.7155/jgaa.00165
%G en
%F JGAA_2008_12_2_a2
Pier Francesco Cortese; Giuseppe Di Battista; Fabrizio Frati; Maurizio Patrignani; Maurizio Pizzonia. C-Planarity of C-Connected Clustered Graphs. Journal of Graph Algorithms and Applications, Tome 12 (2008) no. 2, pp. 225-262. doi : 10.7155/jgaa.00165. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00165/

Cité par Sources :