C-Planarity of C-Connected Clustered Graphs

Authors

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

DOI:

Keywords:

graph drawing, clustered planarity, c-connected clustered graphs, linear-time algorithm, spqr-tree decomposition, bc-tree decomposition

Abstract

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.

Downloads

Download data is not yet available.

Downloads

article (PDF)

Published

2008-06-01

How to Cite

Cortese, P. F., Di Battista, G., Frati, F., Patrignani, M., & Pizzonia, M. (2008). C-Planarity of C-Connected Clustered Graphs.Journal of Graph Algorithms and Applications,12(2), 225–262. https://doi.org/10.7155/jgaa.00165