图绘制 – Peter Eades (悉尼大学)

2018年7月18日(第十届可视化发展前沿研究生暑期学校第三天)上午,来自悉尼大学的Peter Eades教授为暑期学校的学员们做了题为《Graph Drawing》的课程授课。Peter Eades教授于1978从澳大利亚国立大学获博士学位,并在世界各地的大学和研究机构工作。Peter主要研究图绘制,并在1984的论文中[1]首次提出了力导向算法的原型,是图布局最经典的绘制算法。

在课程中,Peter Eades为了大家介绍了图可视化的相关内容。图可视化中最重要的问题就是图布局。简单来讲,图布局就是给拓扑中的节点赋予坐标,并且在节点间用连线表示拓扑中的连接。什么是一个好的图绘制呢?首先,图绘制的结果必须是可信的(faithfulness),即绘制的图能够准确表示原始的数据,但是现在还没有一个正式的规则来评价忠实性;其次,图绘制的结果必须具有可读性(readability),即用户可以准确理解图中的知识信息。好的图布局会避免边交叉,弯曲的边以及节点的重合。

图1. Peter Eades教授介绍平面图的检测算法

接下来,Peter介绍了平面图的概念,一个可以在平面展示而没有交叉边的图称为平面图。根据瓦格纳(Wagner)定理,如果一个图“最小化(minor)”,即将原始图中的边缩成节点,不包含K5和K3,3图,那么这个图就是平面图。K5子图是包含5个节点的全连接图,K3,3图指各集合只包含3个节点的完全二分图。

随后,Peter介绍了正交画法、网格画法等图绘制方法,基于力导向的图布局算法以及大图的谱布局算法。正交画法中所有的边均相互平行或相互正交,网格画法中节点均位于网格中的格点上。两种画法都要从原始图中提取最大平面子图,然后加入其它的边。

力导向算法由Peter本人首先提出,是一种物理模拟方法,每个节点是一个粒子,任意两个粒子之间存在静电斥力,节点之间的连边相当于弹簧,存在弹力。节点在会一致受力方向移动,最终所有节点受力为0,或者系统能量最低时,模拟终止,得到了最后的图布局。为了提高大图的计算效率,可以通过四叉树划分的方式,提高斥力的计算效率。

谱布局是力导向算法的一种,通过计算图的拉普拉斯矩阵,将两个较小的非零特征值对应的特征向量组合作为节点的坐标,对图进行布局。该方法易于理解,计算效率高,但是只适合网格状的图。

图2. Peter Eades教授正在与同学交流

最后,Peter介绍了图布局中仍未有效解决的问题,如何计算图布局的忠实度?如何与大图交互?大图中的边交叉影响大吗?同学们就这些问题与Peter进行了热烈的讨论。课程结束时,袁晓如研究员为Peter Eades教授颁发了纪念铭牌。

图3. 袁晓如研究员为Peter Eades教授颁发纪念铭牌

参考资料:

[1] Peter Eades. A heuristics for graph drawing. Congr. Numer. 42 (1984) 149-160.

评论关闭。