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

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

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

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.ort.shu.edu.cn/EN/10.15960/j.cnki.issn.1007-6093.2015.03.011

https://www.ort.shu.edu.cn/EN/Y2015/V19/I3/85

References

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]	XUE Ling, WU Jianliang. Edge colorings of planar graphs without 5-fans [J]. Operations Research Transactions, 2026, 30(2): 232-236.
[2]	GAO Wei, WANG Weifan. Isolated toughness variant and the existence of fractional [a,b]-factor [J]. Operations Research Transactions, 2026, 30(1): 256-266.
[3]	Xue JI, Liying KANG, Yisai XUE. The extremal problem of spanning linear forests [J]. Operations Research Transactions, 2025, 29(4): 94-102.
[4]	Guidong YU, Hui YUAN, Xinyu XIE. The second largest signless Laplacian spectral radius of uniform supertree with diameter [J]. Operations Research Transactions, 2025, 29(4): 241-248.
[5]	Jiaao LI, Bo SU. Nowhere-zero 5-flows for graphs with bounded genus [J]. Operations Research Transactions, 2025, 29(3): 124-134.
[6]	Minghui YU. Proper polychromatic 4-coloring of subcubic bipartite plane graphs [J]. Operations Research Transactions, 2025, 29(2): 95-102.
[7]	Xintian LIU, Wenxing ZHU. A discrete iterative method for hypergraph bananced bi-partitioning [J]. Operations Research Transactions, 2025, 29(2): 128-140.
[8]	Zhiwei WU, Liying KANG. The extremal p-spectral radius of cancellative hypergraphs [J]. Operations Research Transactions, 2025, 29(2): 194-200.
[9]	Liangli DU, Bing WANG. Planar Turán numbers of {C₅, C₆} [J]. Operations Research Transactions, 2025, 29(2): 221-229.
[10]	Miaohui HE, Xuxiang DUAN, Zhiyou WU. A new algorithm for improving the completion performance of knowledge graph of long-tail data [J]. Operations Research Transactions, 2025, 29(1): 41-54.
[11]	Yao WEN, Junhua HU. Efficiency evaluation for the serial system in the absence of a given leader-follower order in the non-cooperative case [J]. Operations Research Transactions, 2025, 29(1): 77-97.
[12]	Yu YANG, Zhongxun ZHU, Junpeng ZHOU. The extremal k-uniform hypergraphs with given number of pendent vertices on signless Laplacian spectral radius [J]. Operations Research Transactions, 2025, 29(1): 185-197.
[13]	Baoxin LI, Shengjin JI. Total forcing and zero forcing of unicyclic graphs [J]. Operations Research Transactions, 2025, 29(1): 198-206.
[14]	Chaoping WANG, Mengmeng LIU. Steiner k-hyper Wiener index of graph products [J]. Operations Research Transactions, 2025, 29(1): 216-224.
[15]	Linming QI, Weiliang ZHAO, Lianying MIAO. The lower limit of the independence number in edge chromatic critical graphs [J]. Operations Research Transactions, 2025, 29(1): 225-231.

An augmented proximity stress model for edge label overlap removal

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments