Splitting Vertices in 2-Layer Graph Drawings
Splitting Vertices in 2-Layer Graph Drawings
复制标题
分割 2 层图形绘图中的顶点
DOI：
10.1109/mcg.2023.3264244
复制
发表时间：
2023
影响因子：
1.8
通讯作者：
Villedieu, Anaïs
中科院分区：
文献类型：
--
作者：
Ahmed, Reyan;Angelini, Patrizio;Bekos, Michael A.;Battista, Giuseppe Di;Kaufmann, Michael;Kindermann, Philipp;Kobourov, Stephen;Nöllenburg, Martin;Symvonis, Antonios;Villedieu, Anaïs
二分图在几个应用程序中对两个不相交的实体集之间的关系进行建模，并且自然地绘制为2层图形绘图。在这样的图中，两组实体（顶点）被放置在两条平行线（层）上，并且它们的关系（边）由连接顶点的线段表示。构造2层图形的方法通常会尝试最小化边交叉点的数量。我们使用顶点分裂，以减少交叉的数量，通过替换选定的顶点在一个层上的两个（或更多）副本，并适当地分布这些副本之间的事件边缘。我们研究了几个优化问题的顶点分裂，无论是最小化的交叉点的数量或删除所有的交叉点最少的分裂。虽然我们证明了一些变种是NP-完全的，我们得到多项式时间算法的其他人。我们运行我们的算法在一个基准集的二分图代表人类解剖结构和细胞类型之间的关系。
Bipartite graphs model the relationships between two disjoint sets of entities in several applications and are naturally drawn as 2-layer graph drawings. In such drawings, the two sets of entities (vertices) are placed on two parallel lines (layers), and their relationships (edges) are represented by segments connecting vertices. Methods for constructing 2-layer drawings often try to minimize the number of edge crossings. We use vertex splitting to reduce the number of crossings, by replacing selected vertices on one layer by two (or more) copies and suitably distributing their incident edges among these copies. We study several optimization problems related to vertex splitting, either minimizing the number of crossings or removing all crossings with fewest splits. While we prove that some variants areNP-complete, we obtain polynomial-time algorithms for others. We run our algorithms on a benchmark set of bipartite graphs representing the relationships between human anatomical structures and cell types.
登录
查看更多内容
DOI：
10.2200/s01094ed1v01y202104vis012
发表时间：
2021-06
期刊：
--
影响因子：
--
作者：
F. McGee;B. Renoust;D. Archambault;M. Ghoniem;A. Kerren;Bruno Pinaud;M. Pohl;B. Otjacques;G. Melançon;T. V. Landesberger
通讯作者：
F. McGee;B. Renoust;D. Archambault;M. Ghoniem;A. Kerren;Bruno Pinaud;M. Pohl;B. Otjacques;G. Melançon;T. V. Landesberger
顶点分割和无张力布局
DOI：
10.1007/bfb0021804
发表时间：
1995
期刊：
Discret. Math.
影响因子：
--
作者：
P. Eades;Candido Ferreira Xavier de Mendonça Neto
通讯作者：
Candido Ferreira Xavier de Mendonça Neto
覆盖图表的三种方法
DOI：
10.1016/j.disc.2015.10.023
发表时间：
2016
期刊：
Discret. Math.
影响因子：
--
作者：
Kolja B. Knauer;Torsten Ueckerdt
通讯作者：
Torsten Ueckerdt
影响因子：
0.7
作者：
N. Hartsfield;B. Jackson;G. Ringel
通讯作者：
G. Ringel
影响因子：
1.1
作者：
D. Eppstein;Philipp Kindermann;S. Kobourov;G. Liotta;A. Lubiw;A. Maignan;Debajyoti Mondal;H. Vosoughpour;S. Whitesides;S. Wismath
通讯作者：
D. Eppstein;Philipp Kindermann;S. Kobourov;G. Liotta;A. Lubiw;A. Maignan;Debajyoti Mondal;H. Vosoughpour;S. Whitesides;S. Wismath