图像可视化和信息可视化导航：文献综述
Ivan Herman, Member, IEEE Computer Society, Guy MelancËon, and M. Scott Marshall
摘要：这是一个关于图形可视化和导航技术的调查，同时这些技术也在信息可视化中应用。图形出现在很多应用中，比如网页浏览、状态转换关系图和数据结构。在这些可能很大的抽象的图形中可视化和导航的能力通常是一个应用至关重要的一部分。信息可视化有特定需求，这意味着这个调查接近于以一个不同的角度去看待传统图形绘制的结果。
索引词：信息可视化，图形可视化，图形绘制，导航，焦点—整体环境，鱼眼图，聚类
1 介绍
尽管图形可视化是这项调查的主题，但是它不是关于通常所说的图形绘制。优秀的文献调查[4] [34],和书[5]甚至是在线教程[26]都存在图形绘制。相反，处理图形被认为是对信息的可视化。
信息可视化已经成为一个大领域，其子领域也开始出现。（例子参照，Cardet al. [16]在最近十年中收集的论文）一个简单的方法来确定 图形可视化的适用性 是考虑以下问题：在被可视化的数据元素中有没有一种内在的关系？如果问题的答案是没有，那么数据元素是非结构化的，信息可视化系统的目标可能是通过可视化手段帮助发现数据间的关系。然而，如果问题的答案是肯定的那么数据可以被图形的节点所代表，之间的关系可以被边缘所代表。
用信息可视化研究处理非结构数据别有一番风味。然而，这样的研究并不是这个调查的主题。相反，我们的讨论焦点在于结构化数据的表示，比如哪些图是数据最基本的结构表示。信息可视化有特定的需求，这意味着相比于其他调查我们这接近于以一种不同的视角看待传统图形绘制的结果。
2 典型应用领域
图形可视化有很多的应用领域。大部分人已经在一个电脑系统里面遇到过一个文件层次结构。一个文件层次结构可以表示为一个树(一个特殊类型的图形)。通过文件层次结构为了找到一个特定的文件往往需要导航。这样做过的人可能已经经历了一些图形可视化中涉及的问题：”我在什么位置？我要找的文件在哪里？“其他类似的图形类型包括在组织图和分类描述物种间的关系中涉及的层次结构说明。图形的另一个应用是网站地图和浏览记录。在生物学和化学中，图形应用于进化树，系统树，分子地图，遗传图谱，生化途径和蛋白质功能。其他应用领域包括面向对象的系统（类浏览器），数据构特（别是编译器的数据结构），实时系统（状态转换关系图），数据流图，子程序调用图，实体关系图（例如UML和数据库结构），语义网络，知识表示图，项目管理(PERT图)，逻辑编程（SLD树），超大规模集成电路（电路原理图），虚拟现实（场景图）和文件管理系统。注意，并不能总是能保证信息的纯粹的结构格式—–这需要可以处理比树更一般的图的技术。
3 图形可视化中的关键问题
所要观察的图形的大小是图形可视化中的关键问题。大的图形会带来一些难题。如果元素的数量很大，它会使性能降低（妥协）甚至达到平台观察的极限。即使布局和显示所有的元素是可能的，但是可视性或可用性的问题就出现了因为它将变得无法分辨节点和边（见图1，虽然这个树不是非常复杂)。实际上，在辨别问题达到之前，可用性会成为一个问题。众所周知，当所显示的图形比较小时在图形结构中理解和详细分析数据是最简单的。通常，显示整个大图可能指示出总体结构或者其中的位置，但是会变得很难理解。这个问题形成了这个调查的大部分背景。
图1 一个比较大的图的树布局
除了通常提到的信息过载和偶尔提到的格式塔原则，信息可视化的论文很少应用认知科学和人为因素。这不缺乏尝试，当下很少的认知科学的发现被应用到实际，很少有可用性研究已经完成。认知方面无疑是未来研究的主题。因为这个原因，对一个给定的方法的优点进行客观评价变得困难。当各种各样的技术出现时读者必须在心中承受这个限制。
本调查的其余部分组织如下：在第2部分，我们试图给人留下一种印象关于图形布局问题和可扩展性限制。然后我们讨论几个大型图的导航的方法（第三部分），其次是通过重组数据的复杂性减少视觉的方法（第4部分）然后，我们讨论几个应用程序系统使用了在这个调查实现描述的许多技术（第5部分）.为了帮助读者进一步研究和开发，我们列出了不同信息来源，这些信息对于图形可视化非常重要（第6部分）提供了一个广泛的参考列表。
4 图形布局
这部分着眼于图形绘制的当前结果和布局算法，但是在信息可视化中以图形可视化的观点看的。正如我们将要看到的，这种观点在很多方面都不同于图形绘制社区的传统观点。我们将会给可用结果的说明并讨论他们在图形可视化的相关性，尽管通常我们不深入技术细节。对于那些渴望更多信息的人，我们推荐Battista et al[5] 的优秀图书作为最好的起点之一。
5 图形绘制的背景
图绘制社区随着图形绘制座谈会逐年发展，这个会议1992年在罗马发起。Springer-Verlag在LNCS系列上发表了会议记录，其中包含新的布局算法，算法的有效性和局限性的理论结果和系统演示。最近关于图形算法和应用的电子杂志致力于与图形算法和设计有关的论文，以及经验和应用。
基本图形绘制问题简单地说就是：给定一组节点和一组边缘（相关的）计算节点位置和每个边缘的曲线的绘制。当然，这个问题一直存在，原因很简单：一个图形经常由它的绘图所定义。实际上，在他1736年的论文，欧拉自己依靠绘图解决KoÈnigsberger BruÈ cken问题（见Jungnickel【74】的书）
Battista et al. [4]的带注释的书目，收集数以百计的论文研究什么是一个图的好画法。那就是问题变得更加错综复杂之处：它需要通过他们可以应用的图形定义属性和布局分类。例如,一个熟悉的属性是平面化—–是否可以在平面上画图形同时保证没有边缘交叉。布局算法可以根据他们生成的布局类型进行分类。例如用一个整数坐标点实现一个图形的网格布局位置节点。其他布局的分类由他们基于的方法进行定义。比如说，非确定性方式通过使用比如说力引导的模式或者模拟退火算法之类的算法来形成一个分类。图像和布局的每一个层次都产生了一系列问题。比如说，平面性的问题：
对于图像的平面检测：是否有可能在没有边交叉的情况下画一个图？
由不同约束限制的平面输出算法：既然图像是平面的，那就找到一种布局来满足这些约束。
在使用中，许多约束也是 按照 影响最终布局的 美学的规则来表现；比如说，点和边必须均匀分布，每一条边都是相同的长度，边必须是直线，同构子结构相同的方式展示，边的交叉数越少越好。树在文献中是个重要概念。因此，已经增加了额外的美学规则来规划树的表现。比如，同样高度的节点应该置于同一水平线上，兄弟节点之间的距离应该是固定的，等等。想进一步了解这些规则，去看看Battista的书吧。
树的Reingold and Tilford算法就是 达到这些美学标准的 输出算法的好的案例。同构子树是以完全相同的方式进行布局输出的，节点之间的距离是算法的一个参数。另一方面，对于一棵 根据叶节点的数量来组成散布的可用水平空间的 子树，展示一个树的算法越直接和简单，实际上越不能达到以上要求的美学标准。
尽管形容词“美学”在实际中有所应用，但是许多规则是由过去的 更接近实际的问题 引起的。比如说，全图像面积的最小化在许多应用中是很重要的要求。一些规则很明显只适用于图像分类或者图像布局，而其它的规则还有更“绝对”的特性要求。此外，每一个规则都规定了相关的优化问题，而优化问题用于许多非确定性的布局算法。
可是，近来有许多工作都质疑这些规则的绝对性要求的合理性。对于终端用户，可用性研究是用来为了评估这些美学的相关性。Purchase说：减少交叉是迄今为止最重要的美学规则，同时，最小化弯曲的数量并且尽量整齐对称，效果却不是那么好。她的工作按照这些美学标准来排序，可以在Purchase的文献中看到更多的细节。其他的作者发出了对 赖于布局设计的 图像的不同看法。不幸的是，可用性研究需要 理解试验本身和获得合理的分析结果 这两项的好的表现，但是我们把这个行业当成了信息可视化的必须前提。可用性研究在过去在图像可视化公司也倍受信任（也—与上一句进行比较），并且认识到了可用性研究在这个领域中的重要贡献。
与图像绘制相关的多种多样的任务正在研究中，比如说将一个图进行分层、把图像转变成非循环的有向图、图像的平面化、根据布局最小化存储、尽可能减少弯曲的边的数量，等等。不幸的是，许多相关算法对于实际应用来说太复杂了。从好的一面来说，这些任务推动了有效的启发式算法的发展来克服这些问题的复杂性。
在图像可视化中，需要注意的主要问题是图像的大小。能够有效处理几千个节点的系统还是很少见的，尽管大多数应用中的图像都有几千个节点。NicheWorks , GVF , and H3Viewer是 能够处理几千个节点的数据的 算法之中的佼佼者。图像的大小会使得布局算法完全失效。实际上，布局算法会很好的设计图像中的几百个节点，但是这不保证该算法会很好的处理几千个节点。比如说，Fig1显示一个只有几百个节点的树可以使用Reingold and Tilford算法，但几千个节点的树则不行。布局的高密度和改变算法的参数都不能提高图像的表现。其他的2D布局技术能发挥作用，但是大部分布局算法都不能解决这个问题。因为如果布局很紧密，那么图像之间的交互就会变得很困难。图像堵塞使得找寻和定位节点不得不可能。3D的使用和非欧几里德几何也被提出这些问题。2.4和2.5部分会提供关于这些技术更加细节的内容。可是，如果超过准确的限制，没有算法能保证对大图像进行布局设计。这是因为没有足够大的屏幕去显示。实际上，从认知角度而言，根本不足以显示大量的数据。因此，可视化处理的第一步经常是减少显示图像的大小。标准的布局算法仍然使用可视化工具，但是仅限于这些技术相混合时才使用。
当通过图像去定位时，布局算法的其他性能也受到了批评。可预测性的概念在布局算法中被视作重要和必须的概念。对于相同的或者相似的 不应该导致完全不同的视觉表示的图像，可预测性是说算法的两种不同的运行方式。这个性质也被使用者用于保存精神图片的文献中。当标准布局算法分析中，可预测性经常被忽略，而可预测性通常应用于产生图像的静态视图。
另一个重要的问题是复杂性。所有可视化系统都需要提供接近实时的交互，而为了让使用者不感觉到时间很长，更新必须在很短的时间内完成。当打算使用一个算法时，一个算法的时间复杂性的准确评估对于大系统的完成有所帮助。
图2 图形布局算法概述
2.2传统布局—一个综述
为了继续说可预测性和时间复杂度的问题，我们会很简短的复习现在的图像绘制的布局算法。Fig2展示了现存布局技术的分类。这个分类是Mutzel所做。大部分的算法在Battisa的书中有所提示。我们会聚焦于包含一系列布局方式的布局方法。
古典树布局使子节点的位置比他们的祖先的位置要低。这个Reingold and Tilford算法在树的布局算法中可能是最有名的。他能适用于产生从上至下、从左向右的树的布局，也能被设定为输出栅格定位。
H-树布局也是只能表现为平衡树的二叉树的经典代表。Eades提出了通常表现很好的算法的变化。（见图3）Eades提出的径向位置根据节点在树中的深度在同心圆中放置节点。（见图4）一个子树被放置在一个圆的一个扇区内，这个算法保证两个相邻的扇区不会相交（尽管这个条件可被忽略，以此来获得相对更好的设计）。对于一个圆锥树，该算法可以用来获得在平面上鼓起来的效果来替代，以此来表示兄弟子树在一个圆中与父节点相连。这个算法也能直接计算节点的位置，而不需要使用圆锥树。
按照产生清晰的反应层级结构数据的效果上来看，Reingold and Tilford算法能产生更加标准的图绘制局。放射状的树和H-树的点定位在这方面（层次结构）是不同的，这是因为根节点的位置不明确，因此有人想探索图像不分层的方式。Reingold and Tilford、H-树、放射状的树和球状布局都是可预测的。树的布局问题通常有最低的复杂性，而这些树的节点数都是线性的。正如我们所见，尽管树布局框只占Fig2的很小的部分，但是它包含了很多布局方式。Battis的书中章节3.1就是这些树布局技术的进一步综述的好的开始点。两个并非是传统兵工厂部分的树布局算法在这也是很值得一说的：树地图和洋葱图，两者代表了序列的嵌套结构的树。需要重视的是，在树地图中，个别矩阵的大小是很重要的。比如说，如果树代表了一个分层文件结构，那这个大小要与各自的文件的大小成比例。这就是为什么尽管这个结构在该表示法中很难理解，但是树地图在信息可视化中很流行的原因。Wijk和Wetering尝试在树地图缓冲的方式中去克服这个问题。
在图2的底部，一个单独的盒子是致力于平面。在图的绘制中这是一个关键的问题，因为一个图的平面性可能是实际应用施加的一个重要的约束（如代表印刷电路板的图）。对于无向图的平面性的复杂性的测试可以是线性的。（见3.3章在巴蒂斯塔。又见梅尔霍恩和梅素尔[ 88 ]在实施问题的讨论。）然而，许多应用程序施加额外的要求，这要求是边都在相同的方向（平面图中经常使用的一些边缘绕节点避免交叉）。这个情况，称为向上的平面性，将原问题转化为一个NP问题。（见加格和塔马西亚[ 54 ]。参见第6章在巴蒂斯塔等人）。信息可视化中的应用，当处理一个小而稀疏图它仅认识到去检查平面[ 3 ]，[ 30 ]，如通过聚类一个更大的图得到的图的子图（见第4节。）。在一般情况下，我们可以有把握地说，平面不是信息可视化中的一个核心问题。
包括在图2提供的以杉山等人的开创性工作布局一般有向图布局框命名。制定一个有向图的基本方法是首先确定一个分层的节点；即，分配到每个节点的层数和给定层将节点按照一定的顺序。几种不同的分层技术存在，其中大部分依靠的有向无环子图提取。在这一过程中，包含原始图的所有节点的子图是在这样一种方式提取的。这样，当节点被放置在各自的层，边朝着同一方向（通常向下）。另一个解决方案是不提取的子图，但将原图改变方向转换成无环图。
一旦节点被分配到层，同一层必须的定位节点内强加秩序。自从边的交叉已被确认为图的可读性障碍，在交叉边最小化已投入许多精力。这通常是通过在两个连续的层之间最小化边交叉数做成的。这最小化的步骤是在整个算法的复杂度的核心。请注意，这些策略并没有解决最小化整个图的交叉数问题：即使在连续层的限制，边交叉的最小化是困难和复杂的。事实上，GAREY和约翰逊证明这个问题是NP-hard的；伊迪斯和怀特赛斯证明相应的决策问题是NP-完备的。
一个适当最小化的复杂性激发各种启发式开发用于计算在一层节点的一个良好的秩序这个问题发展进步。tutte是第一个提出了一个启发式：从顶部和底部层的顺序，一个节点的坐标被定义为邻节点的重心。这对应于一个节点应保持与邻节点接近这个直观的想法。解决的办法是通过求解线性方程组得到的。这一变化的方案是通过在图形执行层下降低重心坐标计算出来的。更一般地，在图的左面的四盒对应于在Sugiyama布局类算法的各种预处理的可能性。对这个问题有了新的改进和观点最近出版了[ 73 ]，[ 79 ]，这包括对现有技术[ 80 ]和[ 81 ]现有的启发式算法比较的详细报告。
对于有向图的一般方案的关键要素是高度复杂的，虽然图的大小可能是保持在合理范围的，或者我们应该说子图应保持很小。在本身的排名方法按有一个小的代价。事实上，广度优先搜索的图返回一个无环图，可用于分层。然而，这个子图的选择可以决定最终布局的质量。稍后我们将回到那个问题。还不清楚在这个类中的任何算法是否可预测。一些方法具有一定的可预见性，但是要付出的代价需要更大的复杂性由于在同一层重排点而失去弹性。巴蒂斯塔在最小化边交叉的书9章给出了详细介绍。
弹簧布置框代表所有不确定的布局技术，也叫力的方法。伊迪斯第一次提出在图形绘制提出的方法，建模的曲线图的节点和边缘为身体与弹簧。利用虎克定律描述的物体之间的力，他能够生产布局（无向）图。自那时以来，他的方法被重新审视和改进[ 28 ]，[ 47 ]，[ 49 ]，[ 75 ]。在数学上，这种方法是基于一个优化问题。不同的物理模型，导致不同的复杂的算法和它们产生的不同质量的布局。spring的布局已经成功地用于生产均衡的布局图。在某些情况下，他们在没有任何补充的努力下，在相对于最小化边交叉输出甚至可以表现良好。bertault最近开发出一种力导引保持交叉边的模型，把它变成一个更可预测的方法[ 9 ]。
在一般情况下，然而，强有向的方法可以是相当缓慢的。每次迭代都需要访问的所有对的
图中的节点和布局的质量取决于充分的迭代次数：每一步按以下基本的数学模型改进位置。
即使是最好的一个变种，[ 47 ]估计仍然有时间复杂度O…（N3）的工作，其中n是图中的节点的数目。此外，该算法的两个不同的运行在几乎相同的图可能产生从根本上不同的布局。换句话说，这些方法可能是高度不可预测的。这使得他们信息可视化的兴趣少了，因为不可预测性可能是自相互作用一个主要的问题。然而，在某些情况下，如果图小或稀疏缺乏可预见性可以得到补偿，通过动画改变布局来帮助用户在适应新的绘图[ 69 ]。在强有向图方法的更多信息，读者应参阅勃兰登堡等不确定性的技术或在巴蒂斯塔等人的书第10章比较。
我们不会在这里讨论布局网格。我们指的巴蒂斯塔等人的细节，以及学习更多关于其他技术，包括在盒“压实”和“在图2的右侧隆”。这些技术不在图形可视化中发挥核心作用。图2中的分类算法假定布局是仅由节点和边的确定，没有额外的限制。然而，一些工作的应用已经完成，图中的节点在平面上有预先指定的位置，如地理位置。面临的挑战是，然后找一种方法使边缘，例如，采用折线或曲线。
2.3生成树
与现有的技术大部分是一个普遍的问题，他们只适用于相对小图。传统涉及图形绘制成图的可视化相关性少很多，这通常涉及比较大的图。在一般情况下，测试一个平面或尽量减少边交叉几百个节点图是没有意义的。通常，最明显的和实际的解决方案是一个生成树布局图。我们已经已经看到，树布局算法有最低的复杂性和简单的实现。问题是，然后转化成一个找到一个生成树。该选项包括布置图，这基于树包含先前已从图中提取的图形的所有节点的定位。额外的边缘然后添加到树。图论中的文献提出了一长串的算法来计算树图的生成，为定向和无向的情况下（见，例如，容尼克尔[ 74 ]）。顺便说一句，使用生成树布局图也可以解决增益的布局的可预测性。虽然生成树显然不是图形可视化中唯一的布局方法，但是当然他们也将发挥重要的作用。
没有特定的属性提取一个生成树可以很容易做到。
生成树
确定一个生成树没有特定的方法可以轻松地完成，一种可能的办法是广度优先算法遍历图中节点和收集边来形成一棵树，搜索可以从一个结点节点开始, 选择一个结点到其他结点距离最小的作为根结点创建一棵树。 [11]。更复杂的算法设计,以满足不同的优化目标。如果图中存在权, 算法存在计算生成树最小化或最大化树的总权值。一个解决方案是迭代的建立一个树，通过添加临边,每次选择一个边最小(最大)的更新结点。选择不同的权重将产生不同的解决方案,也将影响复杂性(见章节4和5Jungnickel[74])。这个任务的复杂性略有不同。初级的解决方案的复杂度N2†;更好的解决方案复杂度N logN†或E logN†(其中N和E表示图的节点和边的数量)。
加的权不同可以建立不同的生成树，因此,相同的图有不同的布局(尽管实现者必须意识到这样一个事实:一个生成树实现优化目标对于一个给定的权函数不一定产生好的视图)。使用权重也适用于有向无环图,以避免经历交点最小化的任务。对于大型和密集的无环图,使用层作为权值(一个节点或边的重量是其层数) (见,赫尔曼et al)。
3D Layout三维布局
一个流行的方法是显示3 d图形而不是2 d。希望额外的维度将有更多的空间,缓解显示大结构的问题。此外,用户可以操作找到一个没有遮挡的视图。最简单的方法是推广布局算法到3 d。例如,图7显示了一个3 d版本的径向树算法,图8是一个泛化的[104]2d方法嵌套盒[115]。大多数forcedirected方法与维度是独立的关系,允许他们推广到3 d
尽管他们表面上的简单。7和8显示,显示3 d图形也引入了新的问题。3 d对象相互影响,也很难选择最好的视图空间[38]。因此,几乎所有的3 d图形的显示都包括额外的视觉线索,如透明度、深度排队,等。他们还允许用户交互式地改变视图。但是,改变角度带来了另一个困难。常见的做法,比如edge-crossings的最小化,不鼓励如果用户可以改变角度,从另一个角度还可以看到edge-crossings。然而,它,提供最好的视角给用户,所以美学不能被忽略。
锥树,107是最著名的3 d可视化图之一。与前面的例子相反,锥树直接由3d而来,而不是变为2 d算法。
数学上,布局非常简单。结点被放置在一个圆锥的顶点与其孩子均匀放置在它的底部。在最初的实现中,每层都可以有结点,以便减少底层融入的空间。最初的想法锥树已经被其他人实现[20],[59],[71],在某些情况下,还有精致的布局。CarrieAre Kazman[20],例如, 为每个锥近似计算直径通过自底向上遍历树和考虑到后代的数量在每个步骤中以便更好地利用可用的空间。
锥树在交互和视觉方面可用。不仅有一些的明标签的节点,而且用户可以选择任何节点和旋转锥树,以便把节点转到前面。这个也可以有系统自动完成 ,或进一步的用户交互。
获得更多的空间不是唯一的3 d的优势。因为一般人熟悉3 d在物理世界中,3 d有助于创建真实世界在感知复杂的结构上有帮助。最早的广泛应用程序文件系统导航器(参见图10),是与早期SGI工作站到版本5的操作系统。树的布局图(代表用户的文件空间)是一个简单的平面布局。3 d方面,一方面,在平面上添加块的大小和文件大小成比例,另一方面,虚拟景观由那些块组成。这种城市的方法实现在其他系统中,例如,空分复用[24],或者,最近,陈和卡尔提出的系统，更复杂的3 d隐喻包括角度墙[107],代表数据在虚拟空间大墙上的显示。VizNet[43]和维特斯[98]都使用一个想法类似于墙角度，通过将对象映射到一个球体的表面，高度相关对象放置在一起。网络书[15]显示3 d动画书与Web页面内容,等。在这里,我们将概述young的观点[128]为进一步的例子
尽管技术上有不可否认的吸引人的特点，3 d图形可视化技术却有很大的困难。在我们看来,主要原因在于固有的认知困难。知觉和导航冲突差异造成的，由使用2 d屏幕和2 d与3 d交互引起,加上缺少运动信号和立体声信号(见弗兰克[122]这些线索有多重要)。有限的3 d交互,比如旋转一个对象进行检查，而不是接近它, 可以提供3 d交互,不会导致迷失方向。如果采用虚拟现实系统,比如一个工作台,或大图标显示,其中的一些困难可以解决。然而,这样的设施不是广泛使用,仍过于昂贵，作为大多数信息可视化应用程序的基础。当更先进的显示和互动设施(如触觉显示和交互、立体视图等)变得更加广泛,3 d技术可能产生深远的影响在图形可视化方面。
Hyperbolic Layout双曲布局
双曲布局图(主要是树)是其中一个研制的新形式的图布局，可以可视化和交互。第一个论文在这一领域来自Lamping et al。[82],[83], 紧随其后的一系列论文Munzner[92],[93],[94]。例如,发达国家基于网页内容的浏览。也有在技术上使用其他系统的,例如,罗宾逊[108]威尔逊和Bergeron[127]。双曲线的观点,可以在2 d或3 d实现提供了一个扭曲的效果 (参见图11)。它就像使用鱼眼镜头的效果对传统树布局一样。这种扭曲使得与潜在的大空间树的交互成为可能，适合实际的应用程序。 (见3.2节) 我们专注于导航而不是布局时扭曲效果更好。
2.5 双曲布局
图形的双曲布局是图形的新布局格式之一。这些布局是由图形可视化和交互化发展而来的。这一领域的第一篇论文来自于Lamping et al，其后紧接着一系列论文。例如基于这种技术的网络内容视图。这种技术已经在其他系统中被使用，例如Robinson或Wilson&Bergeron。能够由2D或3D实现的双曲线浏览，提供了一个树的扭曲视图（见Fig.11）。在传统树布局上使用鱼眼镜头特效。这种扭曲的视图使我们同潜在的大型树交互成为可能。当我们要关注导航而不是布局的时候我们会在后面提到扭曲效应。
当同其他其他提到的算法比较，双曲线视图在布局上表现了极其不同方向的。这是由于他们不同的几何学背景。事实上，某些经典布局算法可以再双曲线设置中被重复使用，产生一些十分不同的结构，我们随后会做演示。双曲线视图环绕着神秘色彩，因为在信息可视化社区中没有多少人真正理解双曲线可视化的数学基础。此外，复现结果十分困难。不幸的是，还没有论文能够揭示其中的神秘之处。我们将会讨论这些布局方法中的主要元素，希望读者能够更好地理解这些技术。
双曲几何基于一个与传统的欧几里得几何相同的公理体系，除了有一个例外，也就是所谓的第五公理。欧几里得声称如果一条直线与一个点不相交，那么有且只有一直条线过这一点且与第一条直线平行。在双曲几何中则存在多条这样的平行线。传统的三角方程不在有效，三角形的内角和不在为180度。（这些不同之处显示出实现双曲几何中的重大困难）
在欧几里得几何空间中为双曲平面（或空间）定义一个统一的模型，从而使这两个世界具有逻辑上的联系，是可能的。一个模型中定义了欧几里得几何空间中的一个子集，以及“点”，“线”，“交”，“长度”的概念，以便于双曲几何的公理能够在欧几里得几何中是有效的。很多不同的模型被发展起来。最为知名的是Klein和Poincare的模型。Klein模型（见Fig.12）使用了一个开放圆（或者3维中的球形）作为子集。例如，这个模型中双曲平面由圆周上点组成。双曲线由圆周上的弦组成。交就是欧几里得几何中的交。主要的不同是线段的长度。我们在这里不会给出具体定义。长度是圆周上相对点的位置的函数，这样说就足够了。那些在双曲中合理的段指数上小于在欧几里得几何中的。证明所有双曲几何公理的有效性需要一些非凡的努力。考虑途中线L和点P，欧几里得几何第五公理否定的合理性是十分明显的。虽然双曲线由弧所代表，而这些弧与圆周正交，Poincare模型还是相当简单。
我们可以给出双曲图布局正交的精确定义：在双曲平面或空间上执行布局算法，然后在熟悉的欧几里得平面或空间中使用双曲几何模型来显示结果。因此我们看到的本身不是双曲几何，而是在欧几里得几何中的表达。Lamping et al的原始论文中使用了Poincare模型，而Munzner一开始使用了Klein模型。例如在Fig.11中，3维双曲Klein模型被用来显示树。
双曲几何不同的空间本质使得一些简单的布局算法变得可行。例如，考虑下图中树替代算法的轮廓。算法从树的根部开始，递归的用角向量来定位子树。在每一步中，算法用一个楔子来替换一个子树。目的是找到这样一个在不同子树的边之间没有交叉的楔子。如果点P引出一个节点，并且角度为a楔子QPR是被分配格从P开始的子树的一个楔子，则算法的主要步骤是为P的子树定义楔子。角度a被分成几个子角，每一个对应一个子树。
算法非常简单，并且会在欧几里得平面上产生相当少见的图形。实际上，在很多步之后，楔子的角度变得非常小，缩小了下一步中子树可用的空间。然而，如果相同的算法在双曲平面中使用，情况是相当不同的。Fig.14显示了在Klein模型下相同的算法。主要的不同是PQ’和PQ”的平行线被计算出来的方法：平行线与我们模型中的圆周相交。。。
3.导航和交互
在信息可视化中导航和交互是基本设施。没有任何布局算法可以独自克服占据可视化程序的大尺寸图形所引发的问题。此外，显示图形结构的任务需要创新的方法。
3.1 缩放和平移（专业术语）
变焦和pan是可视化中的传统工具。当探索大图结构时，变焦和Pan是必不可少的工具。变焦适合图形，因为被用来显示的图形通常相当简单。这意味着变焦在绝大多数情况下可以通过简单的调整屏幕转换和重绘屏幕内容来完成，而不是在像素图片中变焦。换句话说，没有假信号问题发生。
变焦可以使用两种方式。几何变焦简单的提供图像内容的放大。语义变焦意味着信息内容改变以及在图形特定区域中的细节内容的显示。在这里的技术难度不是变焦操作自身，而是分配适当水平的细节。
虽然概念上很简单，当在交互环境中使用的时候，变焦和Pan产生了一些问题。例如，让我们想象一下接下来的设置：被显示的图形是欧洲的道路网络，用户聚焦到阿姆斯特丹周边的一个区域。用户想要改变米兰周边的视图。在不改变缩放因子的条件下，做这个至少现在太慢，是因为用户必须首先缩小，平移到Milano，再放大。进一步，用户希望系统运作顺畅。一个不现实的实施可能会计算出放大和平移的改变和水平执行的改变。但问题是，放大的时候，世界观成倍扩张速度快，目标点移开的速度比光盘追上的速度快。导致的结果是，目标被不自主接近了：它首先作为缩放支配和只回到中心视图移开，这可能会受扰乱。缩放和平移问题并不限于图形也不是由弗纳斯和Bederson[51]提出以减轻它的解决方案。而且，图形可视化系统可以极大地从他们的做法中受益，所以我们会在这里提供一个简短的描述。弗纳斯和Bederson引入空间尺度图（见图15）的概念。其基本思想是通过生成很多原始的2D图像，尽可能把每一张放大，并把他们堆叠起来，以形成在所述原始图像的反转，以此去定义一个抽象空间。原始图像上的点可以通过光线来代表，光线同时包含关于该信息点及其放大。各种各样的（连续的）缩放的组合和平移操作可以在该空间内被描述为路径，通过描述位于窗口平行与x±y的平板的中心点。成本或是长度也被关联到每个路径，并且如果该长度被明智地选择，最小长度的路径可以表示缩放和平移运动的最佳组合。弗纳斯和Bederson不仅得到了解决上述问题的方案;空间尺度的图表，也可用于描述语义缩放（而不是堆积在金字塔同一图像时，图像的内容可以依赖于放大率） ，这也让一个专业的创作系统的开发语义缩放[52]
3.2 焦点+上下文
关于缩放一个众所周知的问题，如果一个缩放锁定了一个焦点，所有的上下文信息都会丢失。这样的损失可以成为一个相当易用性障碍。有一组技术，其允许用户集中于某些细节，而又不会失去上下文，可以缓解这个问题。术语焦点+上下文已经被用来描述这些技术。他们不更换缩放和平移，而是补充。由于基础数据的复杂性，可能必须放大。然而，FOCUS +环境技术是一个很好的选择，完全成熟的应用系统通常补充他们俩。
鱼眼变形图形的鱼眼视图是流行的焦点+上下文技术。鱼眼的视觉通过放大感兴趣的区域和展示其他细节图像来模仿公知的鱼眼透镜效应（参见图16）。
我们将介绍一些参与了鱼眼技术的数学。在概念上，该图被映射到平面和一个焦点被定义（通常由用户）。从焦点到该树的每个节点的距离，由函数h… X†和扭曲的点来演示，并连接边缘。函数h… X†应该是凹的，映射单调[0,1]区间到[0，1]（参见图17）。由鱼眼视图产生的失真是函数，其具有更快的围绕0的递增（因此影响周围的焦点中的节点）的形式的结果，增量接近1时减速。该函数的确切定义可以产生更低或更强的干扰影响。一个简单失真函数，例如，由萨卡和Brown[110]，[111]所使用的是：H… X†…. D‡1†=…. D‡1= X†（这是标绘在图的功能17）。
系数d是所谓的失真因子，它可以通过使用者交互。It应该是正的设定;它越大，鱼眼失真越强。图18显示出该功能（其中d4）的作用。对于规则方案有一些变化。我们刚才描述的，通常被称为基地干扰，在此意义上，它适用于从焦点开始运动的所有方向上的节点。另一种方法是使用一个ªCartesianº鱼眼：这个距离失真是在建立节点的最终位置之前，独立地应用在x和y方向上。其它变化也是可能的（再次参见图16）。咨询Carpendale等人的意见 [18]或Keahey和罗伯逊[77]最近的例子和他们的视觉效果。最后的选择应取决于图的风格加以探讨，以及在使用的方案。这布局算法简单但功能强大的技术是导航的一种重要形式，补充缩放和平移。然而，实现者应该知道它的陷阱之一。鱼眼视图的本质是扭曲的每个节点的位置。如果干扰被应用，连接节点的边也将被干扰。在数学上，这种失真的结果是一般的曲线。标准图形系统（例如，X11的Java2D，Open GL），不提供必要的设施将一条条线转化为这些曲线（曲线可能相当复杂）。因此实施者的唯一选择，就是去估算高点数的原始线段，改变这些点，最终显示出一条近似理想的转化曲线。问题是近似的点的数量必须相对高，如果图像达到期望值（即平均每边60个点），这会导致过于大量的计算，并且可能使系统接收器的响应达到一个不可接受的低水平。唯一可行的解决方案是仅在节点坐标上应用了鱼眼失真，并且通过直线边缘去连接变换节点。这种不精确的解决结果是意想不到的边交叉点则可能发生（参见，例如，图1的左上象限16B）。当信息可视化项目成为现实时会发生的那些典型的情况之一。如果大量的图表进行了探索，这些额外的交叉点不再那么至关重要，而更重要的是去保持探索工具.。
焦点+背景布局技术的鱼眼镜头技术是独立的布局算法，并定义为一个图形布局的独立处理步骤。用鱼眼交互装置意味着改变聚焦点和/或修改失真值的位置。这种独立设施具有积极和消极的一面。从积极的一面上讲，在鱼眼镜头处于布局模块和实际显示中的管线地方，它允许软件模块化组织运行。鱼眼也可以比布局算法更快，这对于相互作用是一个重要问题。
然而,鱼眼畸变可能破坏管理布局算法的美感。例如,我们已经看到在前面的小节中,它会添加新的不必要的交叉边。另一种方法是建立适当的失真可能性到布局算法本身，从而合并Focus+Context效应和布局合理性。与失真的互动将意味着与（部分）支配布局算法的参数进行交互。双曲布局（见第2.5节）就是这样做的。无论是2D还是3D图像的双曲视图，产生扭曲的视图，而不是不像鱼眼视图（参见图11）。图形鱼眼视图的焦点相对应的是通过Klein 或PoincareÂ模型将双曲视图映射到 欧氏空间的欧氏圆（或球）。与视图交互意味着改变在图中该中心点的位置。
类似的效果可通过使用3D技术来实现（参见2.4节）。通过将物体上的3D表面，例如，通过透视或平行投影在二维屏幕上创建一个自然失真创建视图。在Vitesse的系统[98]，例如，用户只有有限的3D导航设施。映射对象到一个球体或椭球体的主要目标的确实现了Focus+Context下的失真。更复杂的表面（如混合高斯曲线的三维曲面）也已经被用于实现Focus+Context（见Carpendale等人[17]，[18]）。其他的三维可视化技术，已经引用第2.4节（如透视墙[107]），也应用此原则。
双曲线的布局很特别，因为它是以Focus+Context为重点开发失真的图形布局算法。事实上，对于进行过的现有的，和更传统的布局算法以确定这样的依赖于失真的布局是否可行我们没有任何系统的研究，而且，如果可行的话，在实际系统中利用这一性质。尽管一些情况下，应用这种变形控制的可能性显然是可用的。例如，图5用气球布局算法[87]显示了一个平衡树。该算法考虑到后代的数量定义了圆圈的半径。该算法可以很容易地直接给其中一个更大的ªshareº显示空间而收缩其他，从而在圈上创建一个Focus+Context [63]。我们认为，这样的研究将为图形可视化系统的实现提供有价值的输入 。
3.2.3Focus+Context技术的进一步问题
在Focus +Context领域的更近一步研究会是有趣的, 其中一些可能是未来研究的基础（一般表征和失真技术的分类也出现在Leung and Apperly [84]）。例如，鱼眼是基于失真函数的选择，但我们在这里只展示了一个简单的被Sarkar and Brown使用的版本。这个功能可以通过其他不同的失真特征来代替（反正切函数或双曲正切函数，分段线性近似来加快处理速度等）[44]，[77]，[111]。该技术也可以被扩展到三维[19]。此外，正如我们可以谈论“语义缩放”也可以指“语义Focus+Context”也就是说，当变形变得太“极端”，在某种意义上，节点可能会消失。Sarkar and Brown在他们的论文中[110] 描述了这种技术，但更好地控制这个设备可能会导致新的见解。需要注意的是空间尺度图[51]（参见第3.1节），也可以用于模拟鱼眼镜的扭曲，这可能导致有趣的结果通过缩放和平移（语义）鱼眼。最后，多焦点Focus+Context的方法也可以应用于[18]，[76]，[77]，从而使用户能够同时集中在图上的几个 重要的区域或在 一个合作环境[98]中使用该系统。
由谢弗等人[112]提供的一个有趣的例子中 结合了多种技术，包括多焦点的变焦和聚焦+上下文，。我们在第4节讨论他们的系统也显示集群的根本重要性。他们认为已经有一个层次聚类图。图19的左边显示出了初始图。虚线矩形表示逻辑集群（他们出现在图形上仅仅是为了解释，他们不一定会出现一个真正的屏幕上）
该图的右边显示了在同一个图在中聚类A和D上作了多焦zoom/fisheye的操作，这些集群现在更大,而其他集群已经收缩了。此外，作为一种图表上的ªsemantic fisheyeº作用的结果，聚类C已经消失。Schaffer等描述失真和收缩的数学运算来达到上述效果。类似的想法也可以在Huang and Eades [70]的DA±TU系统中找到。然而, 为实现一个条理清晰的导航技术，在结合这些不同的方法上还有许多工作要做来。
3.3增量探测和导航
我们已经强调多次,图的大小是图形可视化应用程序中的一个主要问题。在某些情况下当这样的规模是如此庞大,它就不可能随时处理完整的图,万维网是一个明显的例子。增量勘探技术都非常适合这种情况。系统显示全部图形中的一小部分，其他部分按需要显示。这样的增量方法的优点是, 在某些给定的时间,在屏幕上显示的子图规模可能有限,因此，布局和相互作用时间可能不是关键了。这种图方法探索仍然相对较新, 但是在这方面已经存在有趣的结果，例如参见[14]，[40]，[68]，[69]，[99]，[130].
增量探索意味着系统在图形上放置了一个 可见的“窗口”，有点类似于pan。探索意味着沿着某个轨迹移动窗口（也称为逻辑框架由黄et al .[68]）（参见图20）
这种增量探索本质上有两个方面，即： 决定一个策略，以产生新的逻辑框架 ；重新定位每个变更后逻辑框架的内容。
生成新的逻辑帧总是在用户的控制下。在某些情况下，该逻辑框架简单地包含该节点访问到目前为止。例如，Zeiliger[130]实现的NESTOR工具，，它使用增量探索来记录用户的浏览万维网的历史：新近访问的网页被简单地添加到该逻辑框架，以产生一个新的。 Huang等人。 [68]（同样也实现了一个工具来探索万维网[69]）预测用户的未来互动，不仅加入了一个新的节点，而且加入了它的近邻。 Huang等人[68]或North [99] 还包括对逻辑框架的一部分扔掉的控制,以避免在屏幕上 饱和。
至于重新定位而言，最简单的解决方案是为每个逻辑框架使用相同的布局算法。这样做，例如，Huang等。 [68]。 （请注意，后者使用一种改进的弹簧算法，在屏幕上相对小的图形的情况下，用一个力定向方法在图形可视化是完全可行的。）North [99]和Brandes and Wagner[14]通过更进一步对参数提供动态控制,直接布局算法。
正如上面所说，可视化图形管理这条路还是相当新的，但我们认为它在未来是重要的，它会补充在本次调查中所述的导航和勘探方法。
4聚类
如前面提到的，它有利于减少正在查看的可见元素。限制数量的视觉元素将要显示既提高了清晰度，并同时增加了布局和呈现的性能[78]。各种ª抽象º和ª还原º技术已经被研究人员用来减少的曲线图的视觉复杂。一种方法是进行聚类。
聚类是发现在基于所选择的语义的数据上分组或类的过程。集群技术已经在聚类分析，分组，结块，分类和非监督模式识别[41]，[89] 的文献中提到。我们将参照聚类仅使用图的结构信息作为基于结构的聚类（也称为识别自然簇[109]）。与图形元素执行相关联的语义数据的使用可以被称为基于内容的聚类。
虽然基于内容的聚类可以产生最适合特定应用程序的分组，甚至可以用基于结构的集群相结合，在大多数图形可视化提到集群是纯粹基于结构的集群，有几个明显的例外[91 〕，〔105〕。这可能是由于该基于内容的聚类需要特定应用的数据和知识。基于内容的聚类任何应用可能是针对专门的一个问题域，它在其它应用领域使用不再具有一般化。此外，使用基于结构的聚类的一个优点是，自然簇往往保留原始图的结构，它可以用于用户定位图本身。重要的是要注意，聚类可以用来完成过滤和搜索功能。在可视化方面，滤波通常是指降低重要性或从视图中 去除元素，而搜索通常是指一个元素或元素组的重点。过滤和搜索都可以通过 将元素分成两个或更多的组，然后强调其中一个来实现。
到目前为止最常见的图形可视化聚类方法是找到分离或相互排斥的集群，相对于集群重叠（发现这一过程被称为凝结）。相互分离的集群比重叠的集群容易navigate，因为集群的一个访问者仅访问他们的成员一次。它应该被标注下来，然而，要找到分离的集群并不总是那么可能的，比如在语言或语义拓扑的情况下。
寻找自然集群的方法是选择那些在成员之间拥有最少边的聚类。这个方法是被Mirkin提出来的。它也因为在VLSI设计中被用作Ratio Cut技术而著名。这种技术延伸到当边有权的情况。这个任务然后成为使相互成员的边上的权的总值最小。自然集群也可能被获得通过应用一个弹簧模型。（见下面）
4.1 集群的布局图
在数据中发现集群以后，我们可以减少通过限制我们自身对集群的观察而陈列的元素数量。这提供给我们一个机构的概述，并且让我们清楚它的来龙去脉当减少视觉复杂性时。看最简单和最小的集群图，用户应该能够更好的抓住这个图的整体架构。大多的算法都在寻找在集群数量和在集群中的点的数量的一种平衡。少量的集群允许快速的处理和navigation。然而，数量也不能太少，应为，否则可以看见的信息内容太低。
一种常见的方法是标注带有符号的集群，是他们为super-nodes（超级点）在一个higher-level或compound graph（符合图）中，现在我们可以对他们进行navigate以取代原始的图。一些方法已经被提出，Huang和Eades已经给出一个精确的定义对于边在超级点之间是如何感应的（他们称这个想法为abridgement）。这个技术也已经悄悄被应用到其他可视化领域中。一种原始的方法是删掉边并以一种体现他们相关性的方法放置那些点。这一方法消除了绕边的问题并减少了可视的集群。
如果聚类通过成功的将相同的聚类过程应用于被一个先前的聚类运行发现的集而执行，这一过程被称为层次聚类。一个容量的层级将会来源于层次聚类而且它将会作为一棵树而遍历，在这棵树上每一个集群代表一个节点。结果层次聚类可能被用于引起一个层次在一个图形结构中，否则它可能没有一个层次结构。
讨论到现在为止的方法包括首先发现逻辑簇，然后铺设图的集群。 一种完全不同的方法来聚类是基于力导向的布局。它可以让节点间的力影响在布局中的节点的位置。在所有节点系统中产生排斥其它节点的力，而且其他相关节点被吸引到彼此。经过多次迭代，它们的位置被按照所计算出的力进行调整，系统稳定，产生可视明显的集群。 在一个Narcissus的个案研究中，作者报告说，这种技术可以产生有用的集群在一个相对小数量的迭代中。如与其他N-body问题的复杂性为O(N3)。另一个聚类布局的例子被描述为SemNet系统，在那里聚类是这样完成的，通过使用语义信息来确定节点的定位。
4.2节点度量的聚类
为了画出一个图形，我们必须用数值与节点相关联的措施。一个节点的度量可用于测量或量化一个抽象特征关联于一个节点，以将其与其他人比较相关相同类型和获得的排名。度量作为数字可计算函数。 聚类可以通过根据他们的量度值分配元件组到相应的集来实现。度量还可以用来执行搜索或用于过滤那些具有一定的度量值或高于阈值的值而突出的元素。
术语度量，或节点的度量，已经以许多不同的方式在图形可视化中使用。在本次调查中，我们会用这个词来指代在图中与节点相关的措施。我们已经确定节点度量的概念在文献[11]，[50]，[61]，[78]的几个地方。当然，类似的概念可以应用于与边关联的度量。
度量是基于结构的，如果只使用关于图的结果的信息。度量是基于内容的，如果使用与节点相关联的信息或数据例如文本文档。 结构性量度的优点是，没有域知识是必需的。这使得结构性指标对所有的应用程序有用。这是可能的，当然，将结构度量和基于内容的度量集合以发挥更大的作用是可能的。一个简单的方法是允许用户添加应用程序特定的“weight”到节点，然后与结构度量合并。
结构性量度的一个例子是一个节点的度（即，边连接到节点的数目）。有了这样的度量，应用程序可以唯一地以高于或等于临界值的度来放置这些节点。这将使数据的视图示出了具有与其它节点有最大数量联系的节点。度量标准更具体的树木（称为该Strahler度量[120]）已应用在Fig22，那些拥有高Strahler量度值的节点生成skeleton或被强调的支柱。
度量还可以由于其数字性质而组成。例如，通过选择度量的加权平均值，用户可以选择一个特定功能在形成度量的结果中有多少影响力进而影响对结果聚类。Furnas的DOI功能的度也是一个这样的例子即度量是由其他两个度量组成的（在这种情况下，度量基于距离和详细程度）。
节点的度量可用于许多不同的目的。并且在我们看来，所有可能的应用还没有得到充分开发。例如，度量也可用于管理一个生成树提取程序（见第2.3节）。Furnas的DOI功能已被用来生成图的focus+context视图。在另一应用中度量被用来影响布局。
一旦节点的子集被选中，作为一个骨架，代表着未选择的节点的方法必须被选择。在聚类的情况下，所选择的节点的集合是一组超级节点的集合或它们本身。
Ghosting：不强调节点或节点退居于背景。
Hiding：根本不显示未选择的节点。
这也被称为folding或eliding。
Grouping：一个新的超级节点根据分组的节点
这些方法可以被组合表示。例如，集群用透明的超级节点代表而在IVORY系统中被Sprender等使用。图 22C证明了一个可替代性，其中的大小和字形的形状表示分组而用于指示底层的子图的结构。 由此产生的图中，在技术上复合曲线图，是一种高层次的图或原始图的示意图，对于原始图的遍历有用。
集群是充满挑战的，并且适用于许多不同的领域，其具有不幸的后果是关于聚类结果都散发在期刊和会议针对非常不同的主题。 这使得将成果转化为一个统一的理论或一系列的方法学而变得困难。出人意料的是，一本由Battista等编著的书不包括聚类章节，尽管绘图研讨会每年欢迎这类主题的文章。我们的感觉是，这个问题应受到更多的关注，在未来，尤其是从信息可视化的社区。
5系统
图形可视面积已经达到的一个成熟的水平，基于此大型应用程序和应用程序框架正在发展中。但是，要列举所有的系统是困难的，因为绝对数量。此外，它们其中的一些只有短暂的生命，因为他们是研究工具和其他被嵌入在专门的应用程序中的东西。所有图形可视化系统的概况
将超越本次调查的范围。然而，在前面几节中我们已经提到了很多系统
，基于我们发现有趣或重要的特征。其他一些系统也引起了我们的注意。没有任何其完整性，我们简要描述如下一些额外的系统。
努力开发软件库和框架已经好几个地方已经在进行中。一些库
冲着数学家，其中包括大型算法的库，而另一些则意味着更广泛的应用程序。 有人说是类库和框架是可用的例如GTL [45]，LINK [8]GFC[21]，GDT [55]，和GVF [64]。虽然目前还没有广泛使用的标准为图形提供描述，GML[66]和GraphXML[65]是可用的。
by taoxisun 2014.10.24
………………………………………………………………………
SemNet是少数几个提供图形编辑的系统之一，同时该系统也提供一套完整的大图形可视化工具。它也是我们已知的最早且较完整的系统。
聚类（clustering）被应用于很多较旧的系统，比如SemNet、Narcissus、SKETCH及Navigational View Builder。一些新的图形聚类的系统有，比如NicheWorks、DA-TU、STARLIGHT，Bell实验室使用了一个新系统用于网络可视化。
NicheWorks是一个完整的系统实现的例子，可以在特定的应用中使用它。比如，可用在对Y2K的相关问题进行可视化处理。CarrieÁre和Kazman两人的fsviz系统、不莱梅大学的da Vinci系统及CWI的Latour系统大同小异，是同一类系统。值得一提的是Tom Sawyer Software公司，推出了多款基于各种绘图技术的产品。
下面几种有特性的软件比较突出。STARLIGHT系统是基于内容的聚类，允许实现多个映射和图形布局。它也是少数几个能够将3D图形映射到一个平面区域的系统（将节点或整个图形与地理位置联系起来）。Shiozawa等系统使用了相似的3D变2D的映射，但目的是要在电子表格应用程序中进行观察。另外一个系统，SDM也很独特，是因为它的过滤方法，在该方法中研究者能够通过一张位于城市景观图（a cityscape view）之上的平面提取感兴趣的节点。Chen和Carr两人也使用了类似的节点的城市景观图。系统WebPath在网页历史的3D渲染中使用了雾化效果（a fog effect），其目的是限定观察窗口。图形同样也可以用在帮助我们理解图像及在其上的转换，需要了解的是在这些图像上的边代表操作。Bayesian Belief Networks系统也很吸引人眼球，它为了达到信息量最大化的目的（informative purposes）使用了仿真技术（animation）。Constellation是一套交互性能较高的系统，具有先进的缩放功能，并在促进语言网络（linguistic networks）分析中有突出特点。
World Wide Web，就是一个图形可视化能够在未来扮演重要角色的一个典型应用领域。H3View，基于双曲视图，是SGI公司网站管理工具的一部分，与Lamping等人思想相同，H3View也用在了施乐公司的一个商业衍生品（a commercial spin-off）——Inxight中。by taoxisun 2014.10.24
在研究早期，我们参考了NESTOR和WebOFDAV ,它们可以用在网站导航工具。另一个这种类型的例子，比如Harmony Browser、Mapa或者Fetuccino（后者还将网站搜索引擎的结果和图形可视化进行了结合）。
6.期刊和会议
此研究是基于很多会议和期刊上大量文献综述完成的。该领域一个困难之处就在于研究结果发表在大量不同的出版物上。为了帮助读者认真研究该领域，我们列出了读者可能感兴趣的几种主要出版物，如下：
I. Graph Drawing Symposia（座谈会）每年在不同地方举办。该会议已经演变成了绘图的传统会议。
II. Journal of Graph Algorithms and Applications(JGAA)是一个在线期刊，它收录的文章类似于绘图座谈会。该杂志的主页（home page）是Brown University，但是Oxford University也以图书的形式发布这些文章。
III．绘图和计算几何学及算法有很大关联。因此，如Computational Geometry: Theory and Applications或Algorithmica也可以做参考，尽管这些期刊更偏于数学，因此，期刊中比较难读的是电脑绘图和信息可视化。
IV．每年举办的CHI’XX和UIST’XX都是由ACM SIGCHI赞助发起的，同样也有信息可视化的重要文章。同样的，ACM Transactions on Human Computer Interaction也是重要的文献来源。
V．每年举办的InfoViz’XX symposia已经从IEEE Visualization conference中脱离，形成了一个单独的体系。
VI.同样也有每年举办的 IEEE Conference on Information Visualization会议，但我们认为InfoViz’XX symposia从某种程度上来说更好些。
VII．之前的Eurographics Workshop on Scientific Computing’XX更名为Data Visualization’XX，它将信息可视化作为单独的一部分。该研讨会已经加入了Eurographics IEEE TCVG座谈会，并被认为是IEEE Visualization的姐妹会议。 by taoxisun 2014.10.24
VIII．一些传统的电脑绘图期刊，如IEEE Transactions on Visualization and Computer Graphics或Computer Graphics Forum，其上已经有越来越多的信息可视化文章了。
IX．偏应用的期刊或会议也可能有与他们各自应用领域相关联的信息可视化的文章，比如每年举办的XXth World Wide Web或Digital Library’XX会议。
REFERENCES
[1] C.J. Alpert and A.B. Kahng, ªRecent Developments in Netlist
Partitioning: A Survey,º Integration: The VLSI J., vol. 19, pp. 1-81,
1995.
[2] K. Andrews, ªVisualizing Cyberspace: Information Visualization
in the Harmony Internet Browser,º Proc. IEEE Symp. Information
Visualization (InfoViz ‘95), pp. 97-105, 1995.
[3] P.K. Argawal, B. Aronov, J. Pach, R. Pollack, and M. Sharir,
ªQuasi-Planar Graphs Have a Linear Number of Edges,º Proc.
Symp. Graph Drawing, GD ‘95, pp. 1-7, 1995.
[4] G. di Battista, P. Eades, R. Tamassia, and I.G. Tollis, ªAlgorithms
for Drawing Graphs: An Annotated Bibliography,º Computational
Geometry: Theory and Applications, vol. 4, no. 5, pp. 235-282, 1994.
[5] G. di Battista, P. Eades, R. Tamassia, and I.G. Tollis, Graph
Drawing: Algorithms for the Visualization of Graphs. Prentice Hall,
1999.
[6] R.A. Becker, S.G. Eick, and A.R. Wilks, ªVisualizing Network
Data,º IEEE Trans. Visualization and Computer Graphics, vol. 1, no. 1,
pp. 16-28, 1995.
[7] I. Ben-Shaul, M. Herscovici, M. Jacovi, Y.S. Maarek, D. Pelleg, M.
Shtalhaim, V. Soroka, and S. Ur, ªAdding Support for Dynamic
and Focused Search with Fetuccino,º Proc. Eighth Int’l World Wide
Web Conf., pp. 575-587, 1999.
[8] J. Berry, N. Dean, M. Goldberg, G. Shannon, and S. Skiena, ªGraph
Drawing and Manipulation with LINK,º Proc. Symp. Graph
Drawing GD ‘97, pp. 425-437, 1999.
[9] F. Bertault, ªA Force-Directed Algorithm that Preserves Edge
Crossing Properties,º Proc. Symp. Graph Drawing, GD ‘99, pp. 351-
358, 1999.
[10] J. Blythe, C. McGrah, and D. Krackhardt, ªThe Effect of Graph
Layout on Inference from Social Network Data,º Proc. Symp. Graph
Drawing, GD ‘95, pp. 40-51, 1995.
[11] R.A. Botafogo, E. Rivlin, and B. Schneiderman, ªStructural
Analysis of Hypertexts: Identifying Hierarchies and Useful
Metrics,º ACM Trans. Information Systems, vol. 10, no. 2, 1992.
[12] F.J. Brandenburg, M. Himsolt, and C. Rohrer, ªAn Experimental
Comparison of Force-Directed and Randomized Graph Drawing
Algorithms,º Proc. Symp. Graph Drawing GD ‘95, 1996.
[13] U. Brandes, G. Shubina, and R. Tamassia, ªImproving Angular
Resolution in Visualizations of Geographic Networks,º Data
Visualization ‘2000, Proc. Joint Eurographics and IEEE TCVG Symp.
Visualization, to appear.
[14] U. Brandes and D. Wagner, ªA Bayesian Paradigm for Dynamic
Graph Layout,º Proc. Symp. Graph Drawing GD ‘97, pp. 236-247,
1997.
[15] S.K. Card, G.G. Robertson, and W. York, ªThe WebBook and the
Web Forager: An Information Workspace for the World Wide
Web.º Human Factors in Computer Systems, CHI ‘96 Conf. Proc.,
pp. 111-117, 1996.
[16] Readings in Information Visualization, S.K. Card, J.D. Mackinlay,
and B. Shneiderman, eds. Morgan Kaufmann, 1999.
[17] M.S.T. Carpendale, D.J. Cowperthwaite, and F.D. Fracchia, ª3D
Pliable Surfaces,º Proc. UIST ‘95 Symp., pp. 217-266, 1995.
[18] M.S.T. Carpendale, D.J. Cowperthwaite, F.D. Fracchica, and T.
Shermer, ªGraph Folding: Extending Detail and Context Viewing
into a Tool for Subgraph Comparisons,º Proc. Symp. Graph
Drawing GD ‘95, pp. 127-139, 1996.
[19] M.S.T. Carpendale, D.J. Cowperthwaite, and F.D. Fracchia,
ªExtending Distortion Viewing from 2D to 3D,º IEEE Computer
Graphics and Applications, vol. 17, no. 4, pp. 42-51, 1997.
[20] J. CarrieÁre and R. Kazman, ªResearch Report: Interacting with
Huge Hierarchies: Beyond Cone Trees,º Proc. IEEE Conf. Information
Visualization `95, pp. 74-81, 1995.
[21] C.L. Cesar, Graph Foundation Classes for Java. IBM, http://
www.alphaWorks.ibm.com/tech/gfc, 1999.
[22] C. Chen and L. Carr, ªVisualizing the Evolution of a Subject
Domain: A Case Study,º Proc. IEEE Visualization ‘99 Conf., pp. 449-
452, 1999.
[23] M.C. Chuah, ªDynamic Aggregation with Circular Visual Designs,
º Proc. IEEE Symp. Information Visualization (InfoViz ‘98),
pp. 30-37, 1998.
[24] M.C. Chuah, S.F. Roth, J. Mattis, and J. Kolojejchick, ªSDM:
Malleable Information Graphics,º Proc. IEEE Symp. Information
Visualization, pp. 36-42, 1995.
[25] H.S.M. Coxeter, Introduction to Geometry. John Wiley & Sons, 1973.
[26] I.F. Cruz and R. Tamassia, ªOnline Tutorial on Graph Drawing,º
http://www.cs.brown.edu/people/rt/papers/gd-tutorial/gdconstraints.
pdf. year?
[27] I.F. Cruz and J.P. Twarog, ª3D Graph Drawing with Simulated
Annealing,º Proc. Symp. Graph Drawing GD ‘95, pp. 162-165, 1995.
[28] R. Davidson and D. Harel, ªDrawing Graphs Nicely Using
Simulated Annealing,º ACM Trans. Graphics, vol. 15, no. 4,
pp. 301-331, 1996.
[29] E. Dengler and W. Cowan, ªHuman Perception of Laid-Out
Graphs,º Proc. Symp. Graph Drawing GD ‘98, pp. 441-444, 1998.
[30] A. Denise, M. Vasconcellos, and D.J.A. Welsh, ªThe Random
Planar Graph,º Congressus Numerantium, vol. 113, pp. 61-79, 1996.
[31] C.A. Duncan, M.T. Goodrich, and S.G. Kobourov, ªBalanced
Aspect Trees and Their Use for Drawing Very Large Graphs,º
Proc. Symp. Graph Drawing GD ‘98, pp. 111-124, 1998.
[32] D. Durand and P. Kahn, ªMAPA,º Proc. Ninth ACM Conf.
Hypertext and Hypermedia (Hypertext ‘98), 1998.
[33] P. Eades, ªA Heuristic for Graph Drawing,º Congressus Numerantium,
vol. 42, pp. 149-160, 1984.
[34] P. Eades and K. Sugiyama, ªHow to Draw a Directed Graph,º
J. Information Processing, vol. 13, no. 4, pp. 424-434, 1990.
[35] P. Eades, ªDrawing Free Trees,º Bulletin of the Inst. for Combinatorics
and Its Applications, pp. 10-36, 1992.
[36] P. Eades and S.H. Whitesides, ªDrawing Graphs in Two Layers,º
Theoretical Computer Science, vol. 131, no. 2, pp. 361-374, 1994.
[37] P. Eades and Q.-W. Feng, ªMultilevel Visualization of Clustered
Graphs,º Proc. Symp. Graph Drawing GD ‘96, pp. 101-112, 1997.
[38] P. Eades, M.E. Houle, and R. Webber, ªFinding the Best
Viewpoints for Three-Dimensional Graph Drawings,º Proc. Symp.
Graph Drawing GD ‘97, pp. 87-98, 1998.
[39] S.G. Eick, ªA Visualization Tool for Y2K,º Computer, vol. 31, no. 10,
pp. 63-69, 1998.
[40] J. Eklund, J. Sawers, and R. Zeiliger, ªNESTOR Navigator: A Tool
for the Collaborative Construction of Knowledge through Constructive
Navigation,º Proc. Ausweb ‘99, Fifth Australian World Wide
Web Conf., 1999.
[41] B. Everitt, Cluster Analysis, first ed. Heinemann Educational Books
Ltd., 1974.
[42] K.M. Fairchild, S.E. Poltrock, G.W. Furnas, ªSemNet: Three-
Dimensional Representation of Large Knowledge Bases,º Cognitive
Science and Its Applications for Human-Computer Interaction,
pp. 201-233, Lawrence Erlbaum Assoc., 1988.
[43] K.M. Fairchild, ªInformation Management Using Virtual Reality-
Based Visualisations,º Virtual Reality: Application and Explorations,
Academic Press, 1993.
[44] A. Formella and J. Keller, ªGeneralized Fisheye Views of Graphs,º
Proc. Symp. Graph Drawing GD ‘95, pp. 242-253, 1995.
[45] M. Forster, A. Pick, and M. Raitner, Graph Template Library, Univ.
of Passau, http://infosun.fmi.uni-passau.de/GTL/, 1999.
[46] E. FreÂcon and G. Smith, ªWebPathÐA Three Dimensional Web
History,º Proc. IEEE Symp. Information Visualization (InfoViz ‘98),
1998.
[47] A. Frick, A. Ludwig, and H. Mehldau, ªA Fast Adaptive Layout
Algorithm for Undirected Graphs,º Proc. Symp. Graph Drawing GD
‘93, pp. 389-403, 1994.
[48] M. FroÈhlich and M. Werner, ªDemonstration of the Interactive
Graph Visualization System da Vinci,º Proc. DIMACS Workshop
Graph Drawing ‘94, 1995.
[49] T.M.J. Fruchterman and E.M. Reingold, ªGraph Drawing by
Force-Directed Placement,º SoftwareÐPractice & Experience, vol. 21,
pp. 1,129-1,164, 1991.
[50] G.W. Furnas, ªGeneralized Fisheye Views,º Human Factors in
Computing Systems, CHI ‘86 Conf. Proc., pp. 16-23, 1986.
HERMAN ET AL.: GRAPH VISUALIZATION AND NAVIGATION IN INFORMATION VISUALIZATION: A SURVEY 41
[51] G.W. Furnas and B.B. Bederson, ªSpace-Scale Diagrams: Understanding
Multiscale Interfaces,º Human Factors in Computing
Systems, CHI ‘95 Conf. Proc., pp. 234-241, 1995.
[52] G.W. Furnas and X. Zhang, ªMuSE: A Multi-Scale Editor,º Proc.
UIST ‘98 Symp., 1998.
[53] M.R. Garey and D.S. Johnson, ªCrossing Number is NPComplete,
º SIAM J. Algebraic and Discrete Methods, vol. 4, no. 3,
pp. 312-316, 1983.
[54] A. Garg and R. Tamassia, ªOn the Computational Complexity of
Upward and Rectilinear Planarity Testing,º Proc. Symp. Graph
Drawing, GD ‘95, pp. 286-297, 1995.
[55] Graph Drawing Toolkit. Third Univ. of Rome, http://www.dia.
uniroma3.it/~gdt/, 1999.
[56] C. Gunn, ªVisualizing Hyperbolic Space,º Proc. Eurographics
Workshop Computer Graphics and Math., pp. 299-313, 1992.
[57] B. Hausmann, B. Slopianka, and H.-P. Seidel, ªExploring Plane
Hyperbolic Geometry,º Proc. Workshop Visualization and Math.,
pp. 21-36, 1998.
[58] T. He, ªInternet-Based Front-End to Network Simulator,º Data
Visualization ‘99, Proc. Joint Eurographics and IEEE TCVG Symp.
Visualization, pp. 247-252, 1999.
[59] M. Hemmje, C. Kunkel, and A. Willet, ªLyberWorldÐA Visualization
User Interface Supporting Fulltext Retrieval,º Proc. ACM
SIGIR ‘94, 1994.
[60] R.J. Hendley, N.S. Drew, A.M. Wood, and R. Beale, ªNarcissus:
Visualising Information,º Proc. IEEE Symp. Information Visualization,
pp. 90-96, 1995.
[61] I. Herman, M. Delest, and G. MelancËon, ªTree Visualization and
Navigation Clues for Information Visualization,º Computer
Graphics Forum, vol. 17, no. 2, pp. 153-165, 1998.
[62] I. Herman, M.S. Marshall, G. MelancËon, D.J. Duke, M. Delest, and
J.-P. Domenger, ªSkeletal Images as Visual Cues in Graphs
Visualization,º Data Visualization ‘99, Proc. Joint Eurographics and
IEEE TCVG Symp. Visualization, pp. 13-22, 1999.
[63] I. Herman, G. MelancËon, M.M. de Ruiter, and M. Delest,
ªLatourÐA Tree Visualization System,º Proc. Symp. Graph
Drawing GD ‘99, pp. 392-399, 1999. A more detailed version in:
Reports of the Centre for Math. and Computer Sciences, Report
number INS-R9904, available at: http://www.cwi.nl/InfoVisu/
papers/LatourOverview.pdf, 1999.
[64] I. Herman, M.S. Marshall, and G. MelancËon, ªAn Object-Oriented
Design for Graph Visualization,º Reports of the Centre for Math. and
Computer Sciences, Report no. INS-R0001, available at: http://
www.cwi.nl/InfoVisu/GVF/GVF.pdf, 2000.
[65] I. Herman and M.S. Marshall, ªGraphXML,º Reports of the Centre
for Math. and Computer Sciences, available at: http://www.cwi.nl/
InfoVisu/GVF/GraphXML/GraphXML.pdf, 1999.
[66] M. Himsolt, GMLÐGraph Modelling Language, Univ. of Passau,
http://infosun.fmi.uni-passau.de/Graphlet/GML/, 1997.
[67] J. Hopcroft and R.E. Tarjan, ªEfficient Planarity Testing,º J. ACM,
vol. 21, no. 4, pp. 549-568, 1974.
[68] M.L. Huang, P. Eades, and J. Wang, ªOnline Animated Graph
Drawing Using a Modified Spring Algorithm,º J. Visual Languages
and Computing, vol. 9, no. 6, 1998.
[69] M.L. Huang, P. Eades, and R.F. Cohen, ªWebOFDAVÐNavigating
and Visualizing the Web On-Line with Animated Context
Swapping,º Proc. Seventh World Wide Web Conf., pp. 636-638, 1998.
[70] M.L. Huang and P. Eades, ªA Fully Animated Interactive System
for Clustering and Navigating Huge Graphs,º Proc. Symp. Graph
Drawing GD ‘98, pp. 374-383, 1998.
[71] C.-S. Jeong and A. Pang, ªReconfigurable Disc Trees for
Visualizing Large Hierarchical Information Spaceº Proc. IEEE
Symp. Information Visualization (InfoViz ‘98), 1998.
[72] B. Johnson and B. Schneiderman, ªTree-Maps: A Space-Filling
Approach to the Visualization of Hierarchical Information
Structures,º Proc. IEEE Visualization ‘91, pp. 275-282, 1991.
[73] M. Juenger and P. Mutzel, ª2-Layer Straightline Crossing
Minimization: Performance of Exact and Heuristic Algorithms,º
J. Graph Algorithms and Applications, vol. 1, pp. 33-59, 1997.
[74] D. Jungnickel, Graphs, Networks and Algorithms. Springer Verlag,
1999.
[75] T. Kamada and S. Kawai, ªAn Algorithm for Drawing General
Undirected Graphs,º Information Processing Letters, vol. 31, pp. 7-
15, 1989.
[76] K. Kaugars, J. Reinfelds, and A. Brazma, ªA Simple Algorithm for
Drawing Large Graphs on Small Screens,º Proc. Symp. Graph
Drawing GD ‘94, pp. 278-281, 1995.
[77] T.A. Keahey and E.L. Robertson, ªTechniques for Non-Linear
Magnification Transformations,º Proc. IEEE Symp. Information
Visualization (InfoViz ‘97), pp. 38-45, 1997.
[78] D. Kimelman, B. Leban, T. Roth, and D. Zernik, ªReduction of
Visual Complexity in Dynamic Graphs,º Proc. Symp. Graph
Drawing GD ‘93, 1994.
[79] M.R. Laguna, R. MartõÂ, and V. Vals, ªArc Crossing Minimization
in Hierarchical Digraphs with Tabu Search,º Computers and
Operations Research, vol. 24, no. 12, pp. 1,165-1,186, 1997.
[80] M. Laguna and R. MartõÂ, ªGRASP and Path Relinking for 2-Layer
Straight Line Crossing Minimization,º INFORMS J. Computing,
vol. 11, pp. 44-52, 1999.
[81] M. Laguna and R. MartõÂ, ªHeuristics and Meta-Heuristics for 2-
Layer Straight Line Crossing Minimization,º URL: http://wwwbus.
colorado.edu/Faculty/Laguna/, 1999.
[82] J. Lamping, R. Rao, and P. Pirolli, ªA Focus+context Technique
Based on Hyperbolic Geometry for Visualizing Large Hierarchies,
º Human Factors in Computing Systems, CHI ‘95 Conf. Proc.,
1995.
[83] J. Lamping and R. Rao, ªThe Hyperbolic Browser: A Focus+context
Technique for Visualizing Large Hierarchies,º J. Visual
Languages and Computing, vol. 7, no. 1, pp. 33-55, 1996.
[84] Y.K. Leung and M.D. Apperly, ªA Review and Taxonomy of
Distortion-Oriented Presentation Techniques,º ACM Trans. Computer-
Human Interaction, vol. 1, no. 2, pp. 126-160, 1994.
[85] K.L. Ma, ªImage GraphsÐA Novel Approach to Visual Data
Exploration,º Proc. IEEE Visualization ‘99, pp. 81-88, 1999.
[86] M. McGrath, J. Blythe, and D. Krackhardt, ªThe Effect of Spatial
Arrangement on Judgments and Errors in Interpreting Graphs,º
Social Networks, vol. 19, no. 3, pp. 223-242, 1997.
[87] G. MelancËon and I. Herman, ªCircular Drawings of Rooted
Trees,º Reports of the Centre for Math. and Computer Sciences, report
number INS±9817, available at: http://www.cwi.nl/InfoVisu/
papers/circular.pdf, 1998.
[88] K. Mehlhorn and P. Mutzel, ªOn the Embedding Phase of the
Hopcroft and Tarjan Planarity Testing Algorithm,º Algorithmica,
vol. 16, pp. 233-242, 1996.
[89] B. Mirkin, Mathematical Classification and Clustering. Kluwer
Academic, 1996.
[90] K. Misue, P. Eades, W. Lai, and K. Sugiyama, ªLayout Adjustment
and the Mental Map,º J. Visual Languages and Computing, vol. 6,
pp. 183-210, 1995.
[91] S. Mukherjea, J.D. Foley, and S. Hudson, ªVisualizing Complex
Hypermedia Networks through Multiple Hierarchical Views,º
Human Factors in Computing Systems, CHI ‘95 Conf. Proc., pp. 331-
337, 1995.
[92] T. Munzner and P. Burchard, ªVisualizing the Structure of the
World Wide Web in 3D Hyperbolic Space,º Proc. VRML ‘95 Symp.,
1995.
[93] T. Munzner, ªH3: Laying Out Large Directed Graphs in 3D
Hyperbolic Space,º Proc. 1997 IEEE Symp. Information Visualization
(InfoViz ‘97), pp. 2-10, 1997.
[94] T. Munzner, ªDrawing Large Graphs with H3Viewer and Site
Manager,º Proc. Symp. Graph Drawing GD ‘98, pp. 384-393, 1998.
[95] T. Munzner, F. GuimbretieÁre, and G. Robertson, ªConstellation: A
Visualization Tool for Linguistic Queries from MindNet,º Proc.
IEEE Symp. Information, InfoVis ‘99, pp. 132-135, 1999.
[96] P. Mutzel, C. Gutwengwer, R. Brockenauer, S. Fialko, G. Klau, M.
Kruger, T. Ziegler, S. Naher, D. Alberts, D. Ambras, G. Koch, M.
Junger, C. Bucheim, and S. Leipert, ªA Library of Algorithms for
Graph Drawing,º Proc. Symp. Graph Drawing GD ‘97 Symp.,
pp. 456-457, 1998.
[97] T. Munzner, E. Hoffman, K. Claffy, and B. Fenner, ªVisualizing
the Global Topology of the MBone,º Proc. IEEE Symp. Information
Visualization, 1996.
[98] L. Nigay and F. Vernier, ªDesign Method of Interaction
Techniques for Large Information Space,º Proc. Advanced Visual
Interfaces (AVI ‘98), 1998.
[99] S. North, ªIncremental Layout in DynaDAG,º Proc. Symp. Graph
Drawing GD ‘95, pp. 409-418, 1995.
[100] H.C. Purchase, ªWhich Aesthetic Has the Greatest Effect on
Human Understanding?º Proc. Symp. Graph Drawing GD ‘97,
pp. 248-261, 1998.
[101] H.C. Purchase, R.F. Cohen, and M. James, ªValidating Graph
Drawing Aesthetics,º Proc. Symp. Graph Drawing GD ‘95, pp. 435-
446, 1995.
42 IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, VOL. 6, NO. 1, JANUARY-MARCH 2000
[102] H.C. Purchase, R.F. Cohen, and M. James, ªAn Experimental
Study of the Basis for Graph Drawing Algorithms,º ACM J.
Experimental Algorithmics, vol. 2, no. 4, 1997.
[103] E.M. Reingold and J.S. Tilford, ªTidier Drawing of Trees,º IEEE
Trans. Software Eng., vol. 7, no. 2, pp. 223-228, 1981.
[104] J. Rekimoto and M. Green, ªThe Information Cube: Using
Transparency in 3D Information Visualization,º Proc. Third Ann.
Workshop Information Technologies & Systems (WITS ‘93), 1993.
[105] J.S. Risch, D.B. Rex, S.T. Dowson, T.B. Walters, R.A. May, and B.D.
Moon, ªThe STARLIGHT Information Visualization System,º
Proc. IEEE Conf. Information Visualization, pp. 42-49, 1997.
[106] G.G. Robertson, J.D. Mackinlay, and S.K. Card, ªCone Trees:
Animated 3D Visualizations of Hierarchical Information,º Human
Factors in Computing Systems, CHI ‘91 Conf. Proc., pp. 189-194, 1991.
[107] G.G. Robertson, S.K. Card, and J.D. Mackinlay, ªInformation
Visualization Using 3D Interactive Animation,º Comm. ACM,
vol. 36, no. 4, pp. 57-71, 1993.
[108] A. Robinson, EBI Hyperbolic Viewer. European Bioinformatics Inst.,
available at: http://industry.ebi.ac.uk/~alan/components, 1998.
[109] T. Roxborough and A. Sen, ªGraph Clustering Using Multiway
Ratio Cut,º Proc. Symp. Graph Drawing GD ‘97, pp. 291-296, 1998.
[110] M. Sarkar and M.H. Brown, ªGraphical Fish-Eye Views of
Graphs,º Human Factors in Computing Systems, CHI ‘92 Conf. Proc.,
pp. 83-91, 1992.
[111] M. Sarkar and M.H. Brown, ªGraphical Fisheye Views,º Comm.
ACM, vol. 37, no. 12, pp. 73-84, 1994.
[112] D. Schaffer, Z. Zuo, S. Greenberg, L. Bartram, J. Dill, S. Dubs, and
M. Roseman, ªNavigating Hierarchically Clustered Networks
through Fisheye and Full-Zoom Methods,º ACM Trans. Computer-
Human Interaction, vol. 3, no. 2, pp. 162-188, 1996.
[113] Y. Shiloach, ªArrangements of Planar Graphs on the Planar
Lattices,º PhD thesis, Weizmann Inst. of Science, Rehovot, Israel,
1976.
[114] H. Shiozawa, K.-i. Okada, and Y. Matsushita, ª3D Interactive
Visualization for Inter-Cell Dependencies of Spreadsheets,º Proc.
IEEE Symp. Information Visualization (InfoViz ‘99), pp. 79-82, 1999.
[115] G. Sindre, B. Gulla, and H.G. Jokstad, ªOnion Graphs: Aesthetics
and Layout,º Proc. IEEE/CS Symp. Visual Languages (VL ‘93),
pp. 287-291, 1993.
[116] T.C. Sprenger, M. Gross, D. Bielser, and T. Strasser, ªIVORYÐAn
Object-Oriented Framework for Physics-Based Information Visualization
in Java,º Proc. IEEE Symp. Information Visualization (InfoViz
‘98), 1998.
[117] K. Sugiyama, S. Tagawa, and M. Toda, ªMethods for Visual
Understanding of Hierarchical Systems Structures,º IEEE Trans.
Systems, Man, and Cybernetics, vol. 11, no. 2, pp. 109-125, 1989.
[118] K. Sugiyama and K. Misue, ªVisualization of Structural Information:
Automatic Drawing of Compound Digraphs,º IEEE Transactions
on Systems, Man, and Cybernetics, vol. 21, no. 4, pp. 876-892,
1991.
[119] W. Tutte, ªHow to Draw a Graph,º Proc. London Math. Soc., vol. 3,
no. 13, pp. 743-768, 1963.
[120] X.G. Viennot, ªTrees Everywhere,º Proc. 15th CAAP Conf., pp. 18-
41, 1990.
[121] J.Q. Walker II, ªA Node-Positioning Algorithm for General Trees,º
SoftwareÐPractice and Experience, vol. 20, no. 7, pp. 685-705, 1990.
[122] C. Ware and G. Franck, ªEvaluation of Stereo and Motion Cues for
Visualising Information in Three Dimensions,º ACM Trans.
Graphics, vol. 15, no. 2, pp. 121-140, 1996.
[123] C. Ware, Information Visualization: Perception for Design. Morgan
Kaufmann, 2000.
[124] Y.C. Wei and C.K. Cheng, ªRatio Cut Partitioning for Hierarchical
Designs,º IEEE Trans. Computer-Aided Design, vol. 10, no. 7,
pp. 911-921, 1991.
[125] J.J. van Wijk and H. van de Wetering, ªCushion Treemaps:
Visualization of Hierarchical Information,º Proc. IEEE Symp.
Information Visualization (InfoViz ‘99), pp. 73-78, 1999.
[126] G.J. Wills, ªNiche WorksÐInteractive Visualization of Very Large
Graphs,º Proc. Symp. Graph Drawing GD ‘97, pp. 403-415, 1998.
[127] R.M. Wilson and R.D. Bergeron, ªDynamic Hierarchy Specification
and Visualization,º Proc. IEEE Symp. Information Visualization
(InfoViz ‘99), pp. 65-72, 1999.
[128] P. Young, ªThree Dimensional Information Visualization (Survey),
º Computer Science Technical Report, Centre for Software
Maintenance Dept. of Computer Science, Univ. of Durham,
available at: http://www.dur.ac.uk/~dcs3py/pages/work/
documents/lit-survey/IV-Survey/index.html, 1996.
[129] J.-D. Zapata-Rivera, E. Neufeld, and J.E. Greer, ªVisualization of
Bayesian Belief Networks,º Proc. IEEE Visualization ‘99, Late
Breaking Hot Topics, pp. 85-88, 1999.
[130] R. Zeiliger, ªSupporting Constructive Navigation of Web Space,ºProc. Workshop Personalized and Solid Navigation in Information Space, 1998.
原文+译文的资料下载：
http://download.csdn.net/detail/a1b2c3d4123456/9190999