Advances on Testing C-Planarity of Embedded Flat Clustered Graphs

Chimani, Markus and Di Battista, Giuseppe and Frati, Fabrizio and Klein, Karsten (2014) Advances on Testing C-Planarity of Embedded Flat Clustered Graphs. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 416-427 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_35).

Full text not available from this repository.

Abstract

We show a polynomial-time algorithm for testing c-planarity of embedded flat clustered graphs with at most two vertices per cluster on each face.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_35
Classifications:G Algorithms and Complexity > G.350 Clusters
G Algorithms and Complexity > G.770 Planarity Testing
P Styles > P.180 Cluster
P Styles > P.540 Planar
Z Theory > Z.750 Topology
ID Code:1451

Repository Staff Only: item control page

References

Angelini, P., Di Battista, G., Frati, F., Jelínek, V., Kratochvíl, J., Patrignani, M., Rutter, I.: Testing planarity of partially embedded graphs. In: SODA 2010, pp. 202–221. ACM (2010)

Angelini, P., Frati, F., Patrignani, M. Splitting clusters to get C-planarity. In: Eppstein, D., Gansner, E.R. eds. (2010) Graph Drawing. Springer, Heidelberg, pp. 57-68

Bertolazzi, P., Di Battista, G., Liotta, G., Mannino, C. (1994) Upward drawings of triconnected digraphs. Algorithmica 12: pp. 476-497

Chimani, M., Di Battista, G., Frati, F., Klein, K.: Advances on testing c-planarity of embedded flat clustered graphs. CoRR, abs/1408.2595 (2014)

Chimani, M., Gutwenger, C., Jansen, M., Klein, K., Mutzel, P. Computing maximum c-planar subgraphs. In: Tollis, I.G., Patrignani, M. eds. (2009) Graph Drawing. Springer, Heidelberg, pp. 114-120

Chimani, M., Klein, K. Shrinking the search space for clustered planarity. In: Didimo, W., Patrignani, M. eds. (2013) Graph Drawing. Springer, Heidelberg, pp. 90-101

Cornelsen, S., Wagner, D. (2006) Completely connected clustered graphs. J. Discrete Algorithms 4: pp. 313-323

Cortese, P.F., Di Battista, G., Frati, F., Patrignani, M., Pizzonia, M. (2008) C-planarity of c-connected clustered graphs. J. Graph Algorithms Appl. 12: pp. 225-262

Cortese, P.F., Di Battista, G., Patrignani, M., Pizzonia, M. (2005) Clustering cycles into cycles of clusters. J. Graph Alg. Appl. 9: pp. 391-413

Dahlhaus, E. A linear time algorithm to recognize clustered planar graphs and its parallelization. In: Lucchesi, C.L., Moura, A.V. eds. (1998) LATIN’98: Theoretical Informatics. Springer, Heidelberg, pp. 239-248

Di Battista, G., Frati, F. (2009) Efficient c-planarity testing for embedded flat clustered graphs with small faces. J. Graph Alg. Appl. 13: pp. 349-378

Didimo, W., Giordano, F., Liotta, G. (2008) Overlapping cluster planarity. J. Graph Algorithms Appl. 12: pp. 267-291

Feng, Q.W., Cohen, R.F., Eades, P. Planarity for clustered graphs. In: Moore, W., Luk, W. eds. (1995) Field-Programmable Logic and Applications. Springer, Heidelberg, pp. 213-226

Garg, A., Tamassia, R. (2001) On the computational complexity of upward and rectilinear planarity testing. SIAM Journal on Computing 31: pp. 601-625

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

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

Jelínek, V., Jelínková, E., Kratochvíl, J., Lidický, B. Clustered planarity: Embedded clustered graphs with two-component clusters. In: Tollis, I.G., Patrignani, M. eds. (2009) Graph Drawing. Springer, Heidelberg, pp. 121-132

Jelínek, V., Suchý, O., Tesař, M., Vyskočil, T. Clustered planarity: Clusters with few outgoing edges. In: Tollis, I.G., Patrignani, M. eds. (2009) Graph Drawing. Springer, Heidelberg, pp. 102-113

Jelínková, E., Kára, J., Kratochvíl, J., Pergel, M., Suchý, O., Vyskocil, T. (2009) Clustered planarity: Small clusters in cycles and Eulerian graphs. J. Graph Alg. Appl. 13: pp. 379-422

Kratochvíl, J., Lubiw, A., Nesetril, J. (1991) Noncrossing subgraphs in topological layouts. SIAM J. Discrete Math. 4: pp. 223-244

Schaefer, M. (2013) Toward a theory of planarity: Hanani-Tutte and planarity variants. J. Graph Algorithms Appl. 17: pp. 367-440

Schaeffer, S.E. (2007) Graph clustering. Computer Science Review 1: pp. 27-64

Tamassia, R. (1987) On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16: pp. 421-444