中文

Operations Research Transactions >

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

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

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

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

Cite this article

HU Yifan . An augmented proximity stress model for edge label overlap removal[J]. Operations Research Transactions, 2015 , 19(3) : 85 -95 . DOI: 10.15960/j.cnki.issn.1007-6093.2015.03.011

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.

 
Options
Outlines

/

〈 〉