Clustered Planarity: Embedded Clustered Graphs with Two-Component Clusters

Jelínek, Vít and Jelínková, Eva and Kratochvíl, Jan and Lidický, Bernard (2009) Clustered Planarity: Embedded Clustered Graphs with Two-Component Clusters. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, Heraklion, Crete, Greece , pp. 121-132 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_13).

Full text not available from this repository.

Abstract

We present a polynomial-time algorithm for c-planarity testing of clustered graphs with fixed plane embedding and such that every cluster induces a subgraph with at most two connected components.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-00219-9_13
Classifications:G Algorithms and Complexity > G.350 Clusters
G Algorithms and Complexity > G.770 Planarity Testing
ID Code:902

Repository Staff Only: item control page

References

Cortese, P.F., Di Battista, G., Patrignani, M., Pizzonia, M.: On emb edding a cycle in a plane graph. In: Healy, P., Nikolov, N.S. (eds.) GD 2005, LNCS 3843, pp. 49–60, Springer, Heidelberg (2006)

Cortese, P.F., Di Battista, G., Patrignani, M., Pizzonia, M.: Clustering cycles into cycles of clusters. Journal of Graph Algorithms and Applications, Special Issue on the 2004 Symposium on Graph Drawing, GD 2004. 9(3):391–413 (2005)

Dahlhaus, E.: Linear time algorithm to recognize clustered planar graphs and its parallelization. In: Lucchesi, C. (ed.), LATIN 1998, LNCS, vol. 1380, pp. 239–248, Springer, Heidelberg (1998)

Di Battista, G., Frati, F.: Efficient c-planarity testing for embedded flat clustered graphs with small faces. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007, LNCS, vol. 4875, pp. 291–302, Springer, Heidelberg (2008).

Feng, Q.W., Cohen, R.F., Eades, P.: Planarity for clustered graphs. In: Spirakis, P. (ed.) ESA 1995, LNCS, vol. 979, pp. 213–226, Springer-Verlag (1995)

Goodrich, M.T., Lueker, G.S., Sun, J.Z.: C-planarity of extrovert clustered graphs. In: Healy, P., Nikolov, N.S. (eds.) GD 2005, LNCS 3843, pp. 211–222, Springer, Heidelberg (2006)

Gutwenger, C., Jünger, M., Leipert, S., Mutzel, P., Percan, M., Weiskircher, R.: ¨ Advances in c-planarity testing of clustered graphs. In: Kobourov, S.G., Goodrich, M.T. (eds.) GD 2002, LNCS, vol. 2528, 220–235, Springer, Heidelberg (2002)

Gutwenger, C., Jünger, M., Leipert, S., Mutzel, P., Percan, M., Weiskircher, R.: Subgraph induced planar connectivity augmentation. In: Bodlaender, H.L. (ed.) WG 2003, LNCS, vol. 2880, 261–272, Springer, Heidelberg (2003)

Jelínková, E., Kára, J., Kratochvíl, J., Pergel, M., Suchy, O., Vyskoˇil, T.: Clustered planarity: Small clusters in Eulerian graphs. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007, LNCS, vol. 4875, pp. 303–314, Springer, Heidelberg (2008)