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

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.

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]	TIAN Shuangliang, YANG Huan, SUOLANG Wangqing, YANG Qing. Neighbor sum distinguishing edge coloring of the lexicographic product of paths [J]. Operations Research Transactions, 2020, 24(1): 140-146.
[2]	LI Tong, WANG Guanghui, ZHOU Wenling. A survey on rainbow matchings in graphs and hypergraphs [J]. Operations Research Transactions, 2019, 23(3): 77-90.
[3]	TAO Yanliang, HUANG Qiongxiang, CHEN Lin. Contraction graph method for the interval edge-colorings of graphs [J]. Operations Research Transactions, 2019, 23(2): 31-43.
[4]	LIU Yan, LEI Mengxia, HUANG Xiaoxian. Path-transformation graph of maximum matchings [J]. Operations Research Transactions, 2019, 23(2): 104-112.
[5]	LUO Zhaoyang, SUN Lin. The linear aboricity of planar graphs with 6-cycles containing at most one chord [J]. Operations Research Transactions, 2019, 23(2): 113-119.
[6]	PEI Jianfeng, LIN Shangwei. Two sufficient conditions for maximally restricted-edge-connected hypergraphs [J]. Operations Research Transactions, 2019, 23(2): 120-126.
[7]	SUN Qiushi, YANG Xiaoyun, WANG Ligong, LI Xihe, WANG Pengchao. Laplacian spectral characterizations of new unicyclic graphs H(p,tK_1,m) [J]. Operations Research Transactions, 2019, 23(1): 72-80.
[8]	CHEN Yuanyuan, WANG Guoping. On the signless Laplacian spectral radius of tricyclic graphs [J]. Operations Research Transactions, 2019, 23(1): 81-89.
[9]	CHEN Hongyu, TAN Xiang. An upper bound of the linear 2-arboricity of planar graphs with neither 5-cycles nor adjacent 4-cycles [J]. Operations Research Transactions, 2019, 23(1): 104-110.
[10]	YU Guidong, SUN Wei, LU Xingting. The least eignvalue of the graphs whose complements are connected and have pendant vertices [J]. Operations Research Transactions, 2019, 23(1): 90-96.
[11]	REN Jiamin, FENG Wei, ZHAO Lingqi, WANG Shiying, JIRIMUTU. The 1-good-neighbor diagnosability of the Cayley graphs UG_n generated by unicyclic graphs under the PMC model and the MM^* model [J]. Operations Research Transactions, 2019, 23(1): 97-103.
[12]	DING Chao, YU Guidong. Laplacian spectral characterizations of graphs with even cyclic [J]. Operations Research Transactions, 2018, 22(4): 135-140.
[13]	LV Xuezheng, WEI Erling, SONG Hongye. The basis number of join graphs [J]. Operations Research Transactions, 2018, 22(4): 148-152.
[14]	LI Li, SHAN Erfang. Graph games and edge density of graphs [J]. Operations Research Transactions, 2018, 22(4): 99-107.
[15]	QIN Qiannan, SHAO Yanling. Minimum general sum-connectivity index of tricyclic graphs [J]. Operations Research Transactions, 2018, 22(1): 142-150.

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