一个去除边标签重叠的扩充张力模型

doi:10.15960/j.cnki.issn.1007-6093.2015.03.011

摘要/Abstract

摘要：

在图的最优可视化过程中，当图的边和节点都包含文字或图形标签时，显示这些标签必须保证它们互相不重叠. 这项工作可以融入初始布局的一部分，或作为后处理步骤. 去除重叠的核心问题在于保持布局中固有的结构信息，最大限度地减少所需的额外面积，并保持边尽可能地直. 提出了一种同时去除节点和边的标签重叠的计算方法. 该算法基于最小化一个目标函数，使得图的布局尽少改变，并保持边的平直.

关键词: 可视化, 图, 张力模型

Abstract:

When drawing graphs whose edges and nodes both contain text or graphics, such information needs to be displayed without overlaps, either as part of the initial layout or as a post-processing step. The core problem in removing overlaps lies in retaining the structural information inherent in a layout, minimizing the additional area required, and keeping edges as straight as possible. This paper presents a combined node and edge overlap removal algorithm that aims
at offering one solution to this problem, based on minimizing a cost function that both reduces topological changes to the original drawing, and keeps edges straight.

Key words: visualization, graph, stress model

胡一凡. 一个去除边标签重叠的扩充张力模型[J]. 运筹学学报, 2015, 19(3): 85-95.

HU Yifan. An augmented proximity stress model for edge label overlap removal[J]. Operations Research Transactions, 2015, 19(3): 85-95.

Marriott K, Stuckey P J, Tam V, et al. Removing node overlapping in graph layout using constrained optimization [J]. Constraints, 2003, 8(2):143-171.

Gansner E R, Hu Y F. Efficient, Proximity-Preserving Node Overlap Removal [J]. Journal of Graph Algorithms Applications, 2010, 14: 53-74.

Friedrich C, Schreiber F. Flexible layering in hierarchical drawings with nodes of arbitrary size [C]// Proceedings of the 27th conference on Australasian computer science, Australian Computer Society, 2004, 369-376.

Sugiyama K, Tagawa S, Toda M. Methods for visual understanding of hierarchical systems [J]. IEEE Trans. Systems, Man and Cybernetics, 1981, 11(2): 109-125.

Chuang J H, Lin C C, Yen H C. Drawing graphs with nonuniform nodes using potential fields [C]// Proc. 11th Intl. Symp. on Graph Drawing, London: Springer-Verlag, 2003, 460-465.

Harel D, Koren Y. A fast multi-scale method for drawing large graphs [J]. J. Graph Algorithms and Applications, 2002, 6: 179-202.

Li W, Eades P, Nikolov N. Using spring algorithms to remove node overlapping [C]// Proc. Asia-Pacific Symp. on Information Visualisation, 2005, 131--140.

Wang X, Miyamoto I. Generating customized layouts [C]// Proceedings of the Symposium on Graph Drawing, London: Springer, 1995, 504-515.

Gansner E R, North S C. Improved force-directed layouts [C]// Proc. 6th Intl. Symp. Graph Drawing, London: Springer, 1998, 364-373.

Lyons K~A, Meijer H, Rappaport D. Algorithms for cluster busting in anchored graph drawing [J]. J. Graph Algorithms and Applications, 1998, 2(1).

Edelsbrunner H, M{\"{u}}cke E P. Three-dimensional alpha shapes [J]. ACM Trans. on Graphics, 1994, 13(1): 43--72.

Dwyer T, Marriott K, Stuckey P J. Fast node overlap removal [C]// Proc. 13th Intl. Symp. Graph Drawing, London: Springer, 2006, 8-19.

Hayashi K, Inoue M, Masuzawa T, et al. A layout adjustment problem for disjoint rectangles preserving orthogonal order [C]// Proc. 6th Intl. Symp. Graph Drawing, London: Springer, 1998, 183-197.

Huang X, Lai W. Force-transfer: A new approach to removing overlapping nodes in graph layout [C]// Proc. 25th Australian Computer Science Conference, Australian Computer Society, 2003, 349-358

Misue K, Eades P, Lai W, et al. Layout adjustment and the mental map [J]. J. Vis. Lang. Comput., 1995, 6(2): 183-210.

Hu Y F, Koren Y. Extending the spring-electrical model to overcome warping effects [C]// Proceedings of IEEE Pacific Visualization, IEEE Computer Society, 2009, 129-136.

Christensen J, Marks J, Shieber S. An empirical study of algorithms for point-feature label placement [J]. ACM Transaction On Graphics, 1995, 14: 203-232.

Nascimento H A D, Eades P. User hints for map labeling [J]. Journal of Visual Languages and Computing, 2008, 19(1): 39-74.

Kakoulis K~G, Tollis I G. A unified approach to labeling graphical features [C]// Proceedings of the fourteenth annual symposium on Computational geometry, ACM, New York, USA, 1998, 347-356.

Kakoulis K G, Tollis I G. An algorithm for labeling edges of hierarchical drawings [C]// Proceedings of the 5th International Symposium on Graph Drawing, London: Springer-Verlag, 1997, 169-180.

Kakoulis K G, Tollis I G. On the edge label placement problem [C]//\newblock Proceedings of the Symposium on Graph Drawing, London: Springer-Verlag, 1997, 241-256.

Kakoulis K G, Tollis I G. On the complexity of the edge label placement problem [J]. Computational Geometry Theory Application, 2001, 18(1): 1-17.

Castell\'{o} R, Mili R, Tollis I G. An algorithmic framework for visualizing statecharts [C]// Proceedings of the 8th International Symposium on Graph Drawing, London: Springer-Verlag, 2001, 139-149.

Binucci C, Didimo W, Liotta G, et al. Orthogonal drawings of graphs with vertex and edge labels [J]. Computational Geometry: Theory and Applications, 2005, 32(2): 71-114.

Klau G W, Mutzel P. Combining graph labeling and compaction [C]// Proceedings of the 7th International Symposium on Graph Drawing, London: Springer-Verlag, 1999, 27-37.

Lai W, Eades P. Removing edge-node intersections in drawings of graphs [J]. Information Processing Letters, 2002, 81: 105-110.

Dwyer T, Marriott K, Wybrow M. Integrating edge routing into force-directed layout [C]// Proc. 14th Intl. Symp. Graph Drawing, London: Springer, 2006, 153-164.

Eades P. A heuristic for graph drawing [J]. Congressus Numerantium, 1984, 42: 149-160.

Fruchterman T M J, Reingold E M. Graph drawing by force directed placement [J]. Software - Practice and Experience, 1991, 21: 1129-1164.

Kamada T, Kawai S. An algorithm for drawing general undirected graphs [J]. Information Processing Letters, 1989, 31: 7-15.

Jaromczyk J W, Toussaint G T. Relative neighborhood graphs and their relatives [J]. Proc. IEEE, 1992, 80: 1502-1517.

Gansner E~R, Koren Y, North S C. Graph drawing by stress majorization [C]// Proc. 12th Intl. Symp. Graph Drawing, London: Springer, 2004, 239-250.

[1]	艾江东, 贺凡康, 刘奕航. 2-平衡正则多部竞赛图的强划分解法[J]. 运筹学学报（中英文）, 2026, 30(2): 45-57.
[2]	吴晓宇, 邵虎, 刘鹏杰, 周金诚. 两个充分下降的RMIL型共轭梯度法及图像去噪应用[J]. 运筹学学报（中英文）, 2026, 30(2): 79-92.
[3]	陈涛. t-坚韧图哈密尔顿性的一个充分条件[J]. 运筹学学报（中英文）, 2026, 30(2): 225-231.
[4]	薛玲, 吴建良. 不含F₅作为子图的平面图的边染色[J]. 运筹学学报（中英文）, 2026, 30(2): 232-236.
[5]	刘聪, 简艾伦, 袁功林. 一个应用于图像恢复问题的修正共轭梯度算法[J]. 运筹学学报（中英文）, 2026, 30(1): 207-216.
[6]	高炜, 王维凡. 孤立韧度变种与分数[a,b]-因子存在性[J]. 运筹学学报（中英文）, 2026, 30(1): 256-266.
[7]	季雪, 康丽英, 薛益赛. 生成线性森林的极值问题[J]. 运筹学学报（中英文）, 2025, 29(4): 94-102.
[8]	余桂东, 袁慧, 谢欣宇. 给定直径的超树的第二大无符号拉普拉斯半径[J]. 运筹学学报（中英文）, 2025, 29(4): 241-248.
[9]	李佳傲, 苏博. 亏格有界图的处处非零5-流[J]. 运筹学学报（中英文）, 2025, 29(3): 124-134.
[10]	于明晖. 最大度是3的二部平图的正常多色4-染色[J]. 运筹学学报（中英文）, 2025, 29(2): 95-102.
[11]	刘欣恬, 朱文兴. 超图平衡二划分的离散迭代优化算法[J]. 运筹学学报（中英文）, 2025, 29(2): 128-140.
[12]	吴志伟, 康丽英. 可消去超图p-谱半径的极值问题[J]. 运筹学学报（中英文）, 2025, 29(2): 194-200.
[13]	杜良丽, 王兵. {C₅, C₆}的平面Turán数[J]. 运筹学学报（中英文）, 2025, 29(2): 221-229.
[14]	何苗惠, 段旭祥, 吴至友. 提高长尾数据知识图谱补全性能的一种新算法[J]. 运筹学学报（中英文）, 2025, 29(1): 41-54.
[15]	杨禹, 朱忠熏, 周鋆鹏. 给定悬挂点数的具有最大无符号拉普拉斯谱半径的k一致超图[J]. 运筹学学报（中英文）, 2025, 29(1): 185-197.

一个去除边标签重叠的扩充张力模型

An augmented proximity stress model for edge label overlap removal

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 15

编辑推荐

Metrics

本文评价