Six methods for transforming layered hypergraphs to apply layered graph layout algorithms
Six methods for transforming layered hypergraphs to apply layered graph layout algorithms
复制标题
变换分层超图以应用分层图布局算法的六种方法
DOI：
10.1111/cgf.14538
复制
发表时间：
2022
影响因子：
2.5
通讯作者：
Fekete, Jean‐Daniel
中科院分区：
文献类型：
--
作者：
Di Bartolomeo, Sara;Pister, Alexis;Buono, Paolo;Plaisant, Catherine;Dunne, Cody;Fekete, Jean‐Daniel
超图是图的推广，其中边(超边)可以连接两个以上的顶点-而不是普通图中的边只涉及两个顶点。超图是一种相当常见的数据结构，但对于如何将其可视化却鲜有共识。为了优化超图绘图的可读性，我们需要一个布局算法。常见的图布局算法只考虑普通图，没有考虑超边。我们关注的是分层超图，这是一类特殊的超图，它像分层图一样，将每个顶点分配给一个层，层中的顶点在线性轴上对齐绘制，轴平行排列。本文提出了一种将分层图布局算法应用于分层超图的通用方法。我们为分层超图引入了六种不同的变换。变换的选择在计算性能和结果的可读性方面影响后续的图形布局算法。因此，我们从交叉次数、边缘长度和对性能的影响方面对这些转换进行了比较评估。我们还提供了两个案例研究，展示如何将我们的转换应用于现实生活中的用例。本文件连同所有附录和补充材料可在osf.io/grvwu上查阅。
Hypergraphs are a generalization of graphs in which edges(hyperedges)can connect more than two vertices—as opposed to ordinary graphs where edges involve only two vertices. Hypergraphs are a fairly common data structure but there is little consensus on how to visualize them. To optimize a hypergraph drawing for readability, we need a layout algorithm. Common graph layout algorithms only consider ordinary graphs and do not take hyperedges into account. We focus on layered hypergraphs, a particular class of hypergraphs that, like layered graphs, assigns every vertex to a layer, and the vertices in a layer are drawn aligned on a linear axis with the axes arranged in parallel. In this paper, we propose a general method to apply layered graph layout algorithms to layered hypergraphs. We introduce six different transformations for layered hypergraphs. The choice of transformation affects the subsequent graph layout algorithm in terms of computational performance and readability of the results. Thus, we perform a comparative evaluation of these transformations in terms of number of crossings, edge length, and impact on performance. We also provide two case studies showing how our transformations can be applied to real‐life use cases. A copy of this paper with all appendices and supplemental material is available at osf.io/grvwu.
登录
查看更多内容
使用超图可视化软件工件
DOI：
--
发表时间：
2010
期刊：
Spring conference on Computer graphics
影响因子：
--
作者：
Peter Kapec
通讯作者：
Peter Kapec
DOI：
--
发表时间：
2017
期刊：
arXiv.org
影响因子：
--
作者：
Xavier Ouvrard;J. Goff;S. Marchand
通讯作者：
S. Marchand
DOI：
10.1109/tvcg.2020.3030442
发表时间：
2020-09
影响因子：
5.2
作者：
Sara Di Bartolomeo;Yixuan Zhang;Fangfang Sheng;Cody Dunne
通讯作者：
Sara Di Bartolomeo;Yixuan Zhang;Fangfang Sheng;Cody Dunne
DOI：
--
发表时间：
2004
期刊：
ACM Great Lakes Symposium on VLSI
影响因子：
--
作者：
T. Eschbach;Wolfgang Günther;B. Becker
通讯作者：
B. Becker
影响因子：
64.8
作者：
R. Thurston
通讯作者：
R. Thurston