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

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]	李瞳, 王光辉, 周文玲. 图与超图中的彩色匹配综述[J]. 运筹学学报, 2019, 23(3): 77-90.
[2]	马丽涛, 边伟. 最优传输理论在图像处理中的应用[J]. 运筹学学报, 2019, 23(3): 109-125.
[3]	陶艳亮, 黄琼湘, 陈琳. 图的区间边着色的收缩图方法[J]. 运筹学学报, 2019, 23(2): 31-43.
[4]	刘岩, 雷梦霞, 黄晓娴. 最大匹配的路变换图[J]. 运筹学学报, 2019, 23(2): 104-112.
[5]	罗朝阳, 孙林. 6-圈至多含一弦平面图的线性荫度[J]. 运筹学学报, 2019, 23(2): 113-119.
[6]	裴建峰, 林上为. 极大限制边连通超图的两个充分条件[J]. 运筹学学报, 2019, 23(2): 120-126.
[7]	孙秋实, 杨筱韵, 王力工, 李希赫, 王朋超. 新单圈图H(p,tK_1,m)的拉普拉斯谱刻画[J]. 运筹学学报, 2019, 23(1): 72-80.
[8]	陈媛媛, 王国平. 三圈图的无符号拉普拉斯谱半径[J]. 运筹学学报, 2019, 23(1): 81-89.
[9]	陈宏宇, 谭香. 不含5-圈和相邻4-圈的平面图的线性2-荫度的一个上界[J]. 运筹学学报, 2019, 23(1): 104-110.
[10]	余桂东, 孙威, 芦兴庭. 补图具有悬挂点且连通的图的最小特征值[J]. 运筹学学报, 2019, 23(1): 90-96.
[11]	任佳敏, 冯伟, 赵凌琪, 王世英, 吉日木图. 单圈图生成的凯莱图UG_n在PMC模型和MM^*模型下的1好邻诊断度[J]. 运筹学学报, 2019, 23(1): 97-103.
[12]	丁超, 余桂东. 含偶圈图的Laplacian 谱刻画[J]. 运筹学学报, 2018, 22(4): 135-140.
[13]	吕雪征, 魏二玲, 宋宏业. 联图的圈基[J]. 运筹学学报, 2018, 22(4): 148-152.
[14]	李理, 单而芳. 图上合作博弈和图的边密度[J]. 运筹学学报, 2018, 22(4): 99-107.
[15]	王硕, 朱志斌, 张本鑫. 最小化三个凸函数之和的一个简单原始-对偶算法[J]. 运筹学学报, 2018, 22(2): 127-138.