Planarity for Clustered Graphs
Planarity for Clustered Graphs
复制标题
聚类图的平面性
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
P. Eades
中科院分区：
文献类型：
--
作者：
Qing;R. Cohen;P. Eades
在本文中，我们介绍了一种新的图模型称为聚类图，即图的递归聚类结构。这种图模型在信息科学和数学科学中有许多应用。特别地，我们研究了簇图的C-平面性。给定一个聚集图，C平面性测试问题是确定聚集图是否可以在没有边交叉或边区域交叉的情况下绘制。在本文中，我们提出了有效的算法来测试C-平面性和发现C-平面嵌入的聚类图。
In this paper, we introduce a new graph model known as clustered graphs, i.e. graphs with recursive clustering structures. This graph model has many applications in informational and mathematical sciences. In particular, we study C-planarity of clustered graphs. Given a clustered graph, the C-planarity testing problem is to determine whether the clustered graph can be drawn without edge crossings, or edge-region crossings. In this paper, we present efficient algorithms for testing C-planarity and finding C-planar embeddings of clustered graphs.