How to Draw a Planar Clustered Graph
How to Draw a Planar Clustered Graph
复制标题
如何绘制平面聚类图
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
P. Eades
中科院分区：
文献类型：
--
作者：
Qing;R. Cohen;P. Eades
在本文中，我们介绍并展示了如何绘制一种称为聚类图的实用图结构。我们提出了一种在O（n2.5）时间内生成平面、直线、凸的聚类图的算法。我们还证明了c -平面图直线凸图的面积下界和角度上界。我们表明，这样的图纸需要Ω（2n）的面积，最小的角度是O（1/n）。我们的边界不同于经典图形绘制约定的面积边界和角度边界，其中面积边界为Ω（n2），角度边界是图的最大度的函数。我们的结果表明，直线度和面积之间，以及区域凹凸度和面积之间的重要权衡。
In this paper, we introduce and show how to draw a practical graph structure known as clustered graphs. We present an algorithm which produces planar, straight-line, convex drawings of clustered graphs in O(n2.5) time. We also demonstrate an area lower bound and an angle upper bound for straight-line convex drawings of C-planar graphs. We show that such drawings require Ω(2n) area and the smallest angle is O(1/n). Our bounds are unlike the area and angle bounds of classical graph drawing conventions in which area bound is Ω(n2) and angle bounds are functions of the maximum degree of the graph. Our results indicate important tradeoff between line straightness and area, and between region convexity and area.