Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419168 | Discrete Applied Mathematics | 2007 | 20 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hiroshi Nagamochi, Katsutoshi Kuroya,