Removing Node Overlaps Using Multi-Sphere Scheme

Imamichi, Takashi and Arahori, Yohei and Gim, Jaeseong and Hong, Seok-Hee and Nagamochi, Hiroshi (2009) Removing Node Overlaps Using Multi-Sphere Scheme. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, Heraklion, Crete, Greece , pp. 296-301 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_28).

Full text not available from this repository.

Abstract

In this paper, we consider the problem of removing overlaps of labels in a given layout by changing locations of some of the overlapping labels, and present a new method for the problem based on a packing approach, called multi-sphere scheme. More specifically, we study two new variations of the label overlap problem, inspired by real world applications, and provide a solution to each problem. Our new approach is very flexible to support various operations such as translation, translation with direction constraints, and rotation. Further, our method can support labels with arbitrary shapes in both 2D and 3D layout settings. Our extensive experimental results show that our new approach is very effective for removing label overlaps.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-00219-9_28
Classifications:M Methods > M.999 Others
P Styles > P.060 3D
ID Code:915

Repository Staff Only: item control page

References

Agarwal, P.K., Guibas, L.J., Har-Peled, S., Rabinovitch, A., Sharir, M.: Penetration depth of two convex polytopes in 3D. Nordic Journal of Computing 7(3), 227–240 (2000)

Agrawala, M.: Visualizing Route Maps. Ph.D. thesis, Stanford University (2002)

Ahmed, A., Dwyer, T., Hong, S.H., Murray, C., Song, L., Wu, Y.X.: Visualisation and analysis of large and complex scale-free networks. In: EUROVIS 2005: Eurographics / IEEE VGTC Symposium on Visualization. pp. 239–246 (2005)

Dwyer, T., Marriott, K., Stuckey, P.J.: Fast node overlap removal. In: GD 2005. LNCS, vol. 3843, pp. 153–164 (2006)

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

Hayashi, K., Inoue, M., Masuzawa, T., Fujiwara, H.: A layout adjustment problem for disjoint rectangles preserving orthogonal order. Systems and Computers in Japan 33(2), 31–42 (2002)

Imamichi, T., Arahori, Y., Gim, J.,Hong, S.H., Nagamochi, H.: Removing overlaps in label layouts using multi-sphere scheme. Tech. Rep. 2008-006, Dept. of Applied Mathematics and Physics, Kyoto University (2008)

Imamichi, T., Nagamochi, H.: A multi-sphere scheme for 2D and 3D packing problems. In: SLS 2007. LNCS, vol. 4638, pp. 207–211, Springer, Heidelberg (2007)

Li, W., Eades, P., Nikolov, N.: Using spring algorithms to remove node overlapping. In: APVis 2005. CRPIT, vol. 45, pp. 131–140 (2005)

Liu, D.C., Nocedal, J.: On the limited memory BFGS method for large scale optimization. Mathematical Programming 45(3), 503–528 (1989)

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

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