×

Relaxing the constraints of clustered planarity. (English) Zbl 1315.65015

The authors study a relaxed model of \(c\)-planarity, i.e., \(\langle \alpha, \beta, \gamma \rangle\)-drawings of clustered graphs, where \(\alpha\), \(\beta\), \(\gamma\) are the number of edge-edge, edge-region, region-region crossings, respectively. The study starts with algorithms that produce \(\langle \infty, 0, 0 \rangle\)-, \(\langle 0, \infty, 0\rangle\)- and \(\langle 0, 0, \infty \rangle\)-drawings of clustered graphs if they exist. The algorithms provide upper bounds on the number of crossings for the three kinds of drawings. The authors show that the majority of these upper bounds are tight by providing matching lower bounds. Next, they show that there are clustered graphs admitting drawings with one crossing of a certain type but requiring many crossings in drawing where only different types of crossings are allowed. Then, some complexity results are presented. The authors show three results: (1) minimizing \(\alpha + \beta + \gamma\) in an \(\langle \alpha, \beta, \gamma \rangle\)-drawing is NP-complete even if the underlying graph is planar, (2) minimizing \(\alpha\) in an \(\langle \alpha, 0, 0 \rangle\)-drawing is NP-complete even if the underlying graph is matching, (3) minimizing \(\beta\) in a \(\langle 0, \beta, 0 \rangle\)-drawing is NP-complete even for \(c\)-connected flat clustered graphs in which the underlying graph is a triconnected planar multigraph.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
68R10 Graph theory (including graph drawing) in computer science
05C10 Planar graphs; geometric and topological aspects of graph theory
65Y20 Complexity and performance of numerical algorithms
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Angelini, P.; Di Battista, G.; Frati, F.; Patrignani, M.; Rutter, I., Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph, J. Discrete Algorithms, 14, 150-172 (2012) · Zbl 1247.05156
[2] Angelini, P.; Frati, F.; Patrignani, M., Splitting clusters to get c-planarity, (GD. GD, Lect. Notes Comput. Sci., vol. 5849 (2010)), 57-68 · Zbl 1284.68441
[3] Booth, K. S.; Lueker, G. S., Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms, J. Comput. Syst. Sci., 13, 3, 335-379 (1976) · Zbl 0367.68034
[4] Braß, P.; Cenek, E.; Duncan, C. A.; Efrat, A.; Erten, C.; Ismailescu, D.; Kobourov, S. G.; Lubiw, A.; Mitchell, J. S.B., On simultaneous planar graph embeddings, Comput. Geom., 36, 2, 117-130 (2007) · Zbl 1105.05015
[5] Cornelsen, S.; Wagner, D., Completely connected clustered graphs, J. Discrete Algorithms, 4, 2, 313-323 (2006) · Zbl 1128.05038
[6] Cortese, P. F.; Di Battista, G., Clustered planarity (invited lecture), (Twenty-First Annual Symposium on Computational Geometry (Proc. SoCG 05) (2005), ACM), 30-32
[7] Cortese, P. F.; Di Battista, G.; Frati, F.; Patrignani, M.; Pizzonia, M., C-planarity of c-connected clustered graphs, J. Graph Algorithms Appl., 12, 2, 225-262 (2008) · Zbl 1161.68649
[8] Cortese, P. F.; Di Battista, G.; Patrignani, M.; Pizzonia, M., Clustering cycles into cycles of clusters, J. Graph Algorithms Appl., 9, 3, 391-413 (2005) · Zbl 1161.68650
[9] Cortese, P. F.; Di Battista, G.; Patrignani, M.; Pizzonia, M., On embedding a cycle in a plane graph, Discrete Math., 309, 7, 1856-1869 (2009) · Zbl 1172.05016
[10] Dahlhaus, E., A linear time algorithm to recognize clustered graphs and its parallelization, (Proc. Latin American Theoretical Informatics. Proc. Latin American Theoretical Informatics, Lect. Notes Comput. Sci., vol. 1380 (1998)), 239-248 · Zbl 0905.05074
[11] Di Battista, G.; Didimo, W.; Marcandalli, A., Planarization of clustered graphs, (Mutzel, P.; Juenger, M.; Leipert, S., Graph Drawing (Proc. GD ’01). Graph Drawing (Proc. GD ’01), Lect. Notes Comput. Sci., vol. 2265 (2002)), 60-74 · Zbl 1054.68573
[12] Di Battista, G.; Frati, F., Efficient c-planarity testing for embedded flat clustered graphs with small faces, J. Graph Algorithms Appl., 13, 3, 349-378 (2009) · Zbl 1184.68355
[13] Di Battista, G., On-line maintenance of triconnected components with SPQR-trees, Algorithmica, 15, 4, 302-318 (1996) · Zbl 0843.68088
[14] Di Battista, G.; Tamassia, R., On-line planarity testing, SIAM J. Comput., 25, 956-997 (1996) · Zbl 0858.68063
[15] Erten, C.; Kobourov, S. G., Simultaneous embedding of planar graphs with few bends, J. Graph Algorithms Appl., 9, 3, 347-364 (2005) · Zbl 1161.68664
[16] Feng, Q.; Cohen, R. F.; Eades, P., Planarity clustered graphs, (Proc. European Symposium on Algorithms. Proc. European Symposium on Algorithms, Lect. Notes Comput. Sci., vol. 979 (1995)), 213-226 · Zbl 1512.68214
[17] Feng, Q. W.; Cohen, R. F.; Eades, P., How to draw a planar clustered graph, (COCOON’95. COCOON’95, Lect. Notes Comput. Sci., vol. 959 (1995)), 21-30
[18] Forster, M., Crossings in clustered level graphs (2005), University of Passau, PhD thesis
[19] Garey, M. R.; Johnson, D. S., The rectilinear Steiner tree problem is NP-complete, SIAM J. Appl. Math., 32, 826-834 (1977) · Zbl 0396.05009
[20] Garey, M. R.; Johnson, D. S., Crossing number is NP-complete, SIAM J. Algebr. Discrete Methods, 4, 3, 312-316 (1983) · Zbl 0536.05016
[21] Goodrich, M. T.; Lueker, G. S.; Sun, J. Z., C-planarity of extrovert clustered graphs, (GD. GD, Lect. Notes Comput. Sci., vol. 3843 (2006)), 211-222 · Zbl 1171.68617
[22] Gutwenger, C.; Jünger, M.; Leipert, S.; Mutzel, P.; Percan, M.; Weiskircher, R., Advances in c-planarity testing of clustered graphs, (GD’02. GD’02, Lect. Notes Comput. Sci. (2002)), 220-235 · Zbl 1037.68587
[23] Gutwenger, C.; Mutzel, P., A linear time implementation of SPQR-trees, (Marks, J., Graph Drawing (GD ’00). Graph Drawing (GD ’00), Lect. Notes Comput. Sci., vol. 1984 (2001)), 77-90 · Zbl 1043.68621
[24] Jelínek, V.; Jelínková, E.; Kratochvíl, J.; Lidicky, B., Clustered planarity: embedded clustered graphs with two-component clusters, (GD ’08. GD ’08, Lect. Notes Comput. Sci., vol. 5417 (2008)), 121-132 · Zbl 1213.68459
[25] Jelínek, V.; Suchý, O.; Tesar, M.; Vyskocil, T., Clustered planarity: clusters with few outgoing edges, (GD ’08 (2009)), 102-113 · Zbl 1213.68460
[26] Jelínková, E.; Kara, J.; Kratochvíl, J.; Pergel, M.; Suchý, O.; Vyskocil, T., Clustered planarity: small clusters in Eulerian graphs, (GD ’07. GD ’07, Lect. Notes Comput. Sci., vol. 4875 (2007)), 303-314 · Zbl 1137.68495
[27] Kammer, F., Simultaneous embedding with two bends per edge in polynomial area, (SWAT. SWAT, Lect. Notes Comput. Sci., vol. 4059 (2006)), 255-267 · Zbl 1142.05367
[28] Pach, J.; Tóth, G., Which crossing number is it anyway?, J. Comb. Theory, Ser. B, 80, 2, 225-246 (2000) · Zbl 1023.05042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.