English

运筹学学报 >

2015 , Vol. 19 >Issue 3: 85 - 95

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2015.03.011

运筹学

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

展开
  • 1. 雅虎实验室， 229 W 43街，纽约市，纽约州， 美国

收稿日期: 2015-05-10

  网络出版日期: 2015-09-15

收起

An augmented proximity stress model for edge label overlap removal

Expand
  • 1. Yahoo Labs, 229 W 43rd St, New York City, New York, USA

Received date: 2015-05-10

  Online published: 2015-09-15

Fold

摘要

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

关键词： 可视化; 图; 张力模型

本文引用格式

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

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

参考文献

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.

 
Options
文章导航

/

〈 〉