Drawing c-planar biconnected clustered graphs Original Research Article

In a graph, a cluster is a set of vertices, and two clusters are said to be non-intersecting if they are disjoint or one of them is contained in the other. A clustered graph C consists of a graph G and a set of non-intersecting clusters. In this paper, we assume that C has a compound planar drawing and each cluster induces a biconnected subgraph. Then we show that such a clustered graph admits a drawing in the plane such that (i) edges are drawn as straight-line segments with no edge crossing and (ii) the boundary of the biconnected subgraph induced by each cluster is a convex polygon.