Beyond Clustered Planarity
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Vincenzo Roselli · arXiv (Cornell University) · 2012
In a drawing of a clustered graph vertices and edges are drawn as points and curves, while clusters are represented by simple closed regions. A drawing is c-planar if it has no edge-edge, edge-region, or region-region crossings. An obvious necessary condition for c-planarity is the planarity of the graph underlying the clustered graph. However, planarity is not sufficient and the constraints imposed by the absence of edge-region and of region-region crossings make the family of c-planar graphs too small for some of the typical Graph Drawing application contexts. Hence, we relax such constraints and define and study $ $-drawings of \cgs whose underlying graph is planar. In an $ $-drawing the number of edge-edge, edge-region, and region-region crossings is equal to $\alpha$, $\beta$, and $\gamma$, respectively. In this context $ $-drawings are a generalization of c-planar drawings, where $\alpha=\beta=\gamma=0$.