Convex Drawing for c-Planar Biconnected Clustered Graphs

Nagamochi, Hiroshi and Kuroya, Katsutoshi (2004) Convex Drawing for c-Planar Biconnected Clustered Graphs. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003 , pp. 369-380(Official URL:

Full text not available from this repository.


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 is a graph with a set of non-intersecting clusters. In this paper, we assume that the graph is planar, each non leaf cluster has exactly two child clusters in the tree representation of non-intersecting clusters, 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 crossing between two edges, and (ii) the boundary of the biconnected subgraph induced by each cluster is convex polygon.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-24595-7_34
Classifications: P Styles > P.720 Straight-line
P Styles > P.180 Cluster
G Algorithms and Complexity > G.350 Clusters

Actions (login required)

View Item View Item