Efficient Node Overlap Removal Using a Proximity Stress Model

Gansner, Emden R. and Hu, Yifan (2009) Efficient Node Overlap Removal Using a Proximity Stress Model. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, Heraklion, Crete, Greece , pp. 206-217 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_20).

Full text not available from this repository.

Abstract

When drawing graphs whose nodes contain text or graphics, the nontrivial node sizes must be taken into account, either as part of the initial layout or as a post-processing step. The core problem is to avoid overlaps while retaining the structural information inherent in a layout using little additional area. This paper presents a new node overlap removal algorithm that does well by these measures.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-00219-9_20
Classifications:G Algorithms and Complexity > G.560 Geometry
D Aesthetics > D.999 Others
ID Code:942

Repository Staff Only: item control page

References

Borg, I., Groenen, P.: Modern Multidimensional Scaling: Theory and Applications. Springer; Heidelberg (1997)

Chuang, J.H., Lin, C.C., Yen, H.C.: Drawing graphs with nonuniform nodes using potential fields. In: Stinson, D.R., Tavares, S.(eds.) SAC 2000. LNCS, vol. 2012, pp. 460–465. Springer, Heidelberg(2001)

Dwyer, T., Marriott, K., Stuckey, P.J.: Fast node overlap removal. In: Healy, P., Nikolov, N.S. (eds.) LNCS, vol. 3843, pp. 153–164. Springer, Heidelberg (2006)

Eades, P.: A heuristic for graph drawing. Congressus Numerantium 42, 149–160 (1984)

Erten, C., Efrat, A., Forrester, D., Iyer, A., Kobourov, S.G.: Force-directed approaches to sensor network localization. In: Raman, R., Sedgewick, R., Stallmann, M.F. (eds.) Proc. 8th Workshop Algorithm Engineering and Experiments(ALENEX). pp. 108–118. SIAM, Philadelphia (2006)

Fortune, S.: A sweepline algorithm for Voronoi diagrams. Algorithmica 2, 153–174 (1987)

Fruchterman, T.M.J., Reingold, E.M.: Graph drawing by force directed placement. Software - Practice and Experience 21, 1129–1164 (1991)

Gansner, E.R., Koren, Y., North, S.C.: Graph drawing by stress majorization. In: Pach, J. GD 2004. LNCS, vol. 3383, pp. 239–250. Springer, Heidelberg (2005)

Gansner, E.R., North, S.: An open graph visualization system and its applications to software engineering. Software - Practice & Experience 30, 1203–1233(2000)

Gansner, E.R., North, S.C.: Improved force-directed layouts. In: Whitesides, S.H.(ed.) GD 1998 LNCS, vol. 1547, pp. 364–373. Springer, Heidelberg (1999)

Gower, J.C., Dijksterhuis, G.B.: Procrustes Problems. Oxford University Press, Oxford (2004)

Guibas, L., Stolfi, J.: Primitives for the manipulation of general subdivisions and the computation of voronoi. ACM Trans. Graph. 4(2), 74–123 (1985)

Harel, D., Koren, Y.: A fast multi-scale method for drawing large graphs. J. Graph Algorithms and Applications 6, 179–202 (2002)

Hayashi, K., Inoue, M., Masuzawa, T., Fujiwara, H.: A layout adjustment problem for disjoint rectangles preserving orthogonal order. In: Whitesides, S.H.(ed.)GD 1998. LNCS, vol. 1547, pp. 183–197. Springer; Heidelberg (1999)

Hu, Y.F.: Drawings of the mathematics genealogy project graphs. http://www.research.att.com/˜yifanhu/GALLERY/MATH GENEALOGY

Hu, Y.F.: Efficient and high quality force-directed graph drawing. Mathematica Journal 10, 37–71 (2005)

Huang, X., Lai, W.: Force-transfer: A new approach to removing overlapping nodes in graph layout. In: Proc. 25th Australian Computer Science Conference. pp. 349–358 (2003),

URL citeseer.ist.psu.edu/564050.html

Jaromczyk, J.W., Toussaint, G.T.: Relative neighborhood graphs and their relatives. Proc. IEEE 80, 1502–1517 (1992)

Kamada, T., Kawai, S.: An algorithm for drawing general undirected graphs. Information Processing Letters 31, 7–15 (1989)

Leach, G.: Improving worst-case optimal Delaunay triangulation algorithms. In: 4th Canadian Conference on Computational Geometry. pp. 340–346 (1992), URL citeseer.ist.psu.edu/leach92improving.html

Li, W., Eades, P., Nikolov, N.: Using spring algorithms to remove node overlapping. In: Proc. Asia-Pacific Symp. on Information Visualisation. pp. 131–140 (2005)

Lyons, K.A., Meijer, H., Rappaport, D.: Algorithms for cluster busting in anchored graph drawing. J. Graph Algorithms and Applications 2(1) (1998)

Marriott, K., Stuckey, P.J., Tam, V., He, W.: Removing node overlapping in graph layout using constrained optimization. Constraints 8(2), 143–171 (2003)

Department of mathematics at North Dakota State University: The mathematics genealogy project. http://genealogy.math.ndsu.nodak.edu/

Misue, K., Eades, P., Lai, W., Sugiyama, K.: Layout adjustment and the mental map. J. Vis. Lang. Comput. 6(2), 183–210 (1995)

Wang, X., Miyamoto, I.: Generating customized layouts. In: Brandenburg, F.J. (ed.)GD 1995: Proceedings of the Symposium on Graph Drawing. LNCS, vol. 1027, pp. 504–515. Springer, Heidelberg (1995)