Drawing c-planar biconnected clustered graphs |
| |
Authors: | Hiroshi Nagamochi Katsutoshi Kuroya |
| |
Affiliation: | a Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Sakyo, Kyoto 606-8501, Japan b Hitachi Advanced Digital, Inc., 292 Yoshida-cho, Totsuka-ku, Yokohama 244, Japan |
| |
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. |
| |
Keywords: | Algorithm Clustered graph Divide-and-conquer Graph drawing Planar graph |
本文献已被 ScienceDirect 等数据库收录! |
|