Clustered Planarity: Clusters with Few Outgoing Edges

Jelínek, Vít and Suchý, Ondrej and Tesar, Marek and Vyskocil, Tomás (2009) Clustered Planarity: Clusters with Few Outgoing Edges. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, Heraklion, Crete, Greece , pp. 102-113 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_11).

Full text not available from this repository.

Abstract

We present a linear algorithm for c-planarity testing of clustered graphs, in which every cluster has at most four outgoing edges.

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

Repository Staff Only: item control page

References

Cornelsen, S. and Wagner, D.: Completely connected clustered graphs. In: Journal of Discrete Algorithms 4(2), 313–323 (2006)

Cortese, P. F. and Di Battista, G.: Clustered planarity. In: ACM SoCG 2005, pp. 32–34 (2005)

Cortese, P. F., Di Battista, G., Patrignani, M., Pizzonia, M.: Clustering cycles into cycles of clusters. In: Journal of Graph Algorithms and Applications, GD 04, 9(3), 391–413 (2005)In: Pachm J.(ed.) GD 2004. LNCS, vol. 3383, pp. 391- 413. SDpringer, Heidelberg (2005)

Dahlhaus, E.: Linear time algorithm to recognize clustered planar graphs and its parallelization. In: Lucchesi, C. (ed.) LATIN ’98, 3rd Latin American symposium on theoretical informatics, Campinas, Brazil, April 20-24, 1998, LNCS, vol.1380, pp. 239–248, 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)

Eades, P., Feng, Q. W., Lin, X., Nagamochi, H.: Straight-line drawing algorithms for hierarchical graphs and clustered Graphs. In: Algorithmica 44, pp. 1–32 (2006)

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

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

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

Gutwenger, C., Jünger, M., Leipert, S., Mutzel, P., Percan, M., Weiskircher, R.: ¨ Subgraph induced planar connectivity augmentation. In: WG 2003, LNCS, vol. 2880, pp. 261–272, Springer-Verlag (2003)

Hopcroft, J. and Tarjan, R. E.: Efficient planarity testing. In: J. ACM, 21(4), 549–568 (1974)

Jelínková, E., Kára, J., Kratochvíl, J., Pergel, M., Suchý, O., Vyskocil, T.: Clusı a a ı ´ c tered planarity: Small clusters in eulerian graphs. In: Hongi, S., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 303–314. Springer, Heidelberg (2008)