Relaxing the constraints of clustered planarity (Q2261574)

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.