Generalizing Geometric Graphs

Brunel, Edith and Gemsa, Andreas and Krug, Marcus and Rutter, Ignaz and Wagner, Dorothea (2012) Generalizing Geometric Graphs. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 179-190 (Official URL:

Full text not available from this repository.


Network visualization is essential for understanding the data obtained from huge real-world networks such as flight-networks, the AS-network or social networks. Although we can compute layouts for these networks reasonably fast, even the most recent display media are not capable of displaying these layouts in an adequate way. Moreover, the human viewer may be overwhelmed by the displayed level of detail. The increasing amount of data therefore requires techniques aiming at a sensible reduction of the visual complexity of huge layouts. We consider the problem of computing a generalization of a given layout reducing the complexity of the drawing to an amount that can be displayed without clutter and handled by a human viewer. We take a first step at formulating graph generalization within a mathematical model and we consider the resulting problems from an algorithmic point of view. Although these problems are NP-hard in general, we provide efficient approximation algorithms as well as efficient and effective heuristics. At the end of the paper we showcase some sample generalizations.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_18
Classifications:Z Theory > Z.250 Geometry
ID Code:1252

Repository Staff Only: item control page


Abello, J., Kobourov, S.G., Yusufov, R.: Visualizing Large Graphs with Compound-Fisheye Views and Treemaps. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 431–441. Springer, Heidelberg (2005)

Abello, J., Korn, J., Finocchi, I.: Graph sketches. In: Proceedings of the IEEE Symposium on Information Visualization 2001 (INFOVIS 2001), p. 67. IEEE Computer Society (2001)

Bentley, J.L., Saxe, J.B.: Decomposable searching problems I. static-to-dynamic transformation. Journal of Algorithms 1(4), 301–358 (1980)

Bohn, R.E., Short, J.E.: How much information? 2009 Report on American consumers. Global Information Industry Center, University of California, San Diego (2009)

Brandes, U., Delling, D., Gaertler, M., Görke, R., Hoefer, M., Nikoloski, Z., Wagner, D.: On modularity clustering. IEEE Trans. Knowledge and Data Engineering 20, 172–188 (2008)

Brunel, E., Gemsa, A., Krug, M., Rutter, I., Wagner, D.: Generalizing Geometric Graphs. Technical Report 27, Karlsruhe Institute of Technology (2011)

Chazelle, B., Cole, R., Preparata, F.P., Yap, C.: New upper bounds for neighbor searching. Information and Control 68(1-3), 105–124 (1986)

Chazelle, B.: Functional approach to data structures and its use in multidimensional searching. SIAM J. Comput. 17, 427–462 (1988)

Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Mathematics 86(1-3), 165–177 (1990)

Davis, T.A.: University of florida sparse matrix collection. NA Digest 92 (1994)

de Berg, M., Khosravi, A.: Optimal Binary Space Partitions in the Plane. In: Thai, M.T., Sahni, S. (eds.) COCOON 2010. LNCS, vol. 6196, pp. 216–225. Springer, Heidelberg (2010)

Dobkin, D., Friedman, S., Supowit, K.: Delaunay graphs are almost as good as complete graphs. Discrete & Computational Geometry 5, 399–407 (1990)

Eades, P., Feng, Q.-W.: Multilevel Visualization of Clustered Graphs. In: North, S.C. (ed.) GD 1996. LNCS, vol. 1190, pp. 101–112. Springer, Heidelberg (1997)

Edelsbrunner, H., Guibas, L., Sharir, M.: The upper envelope of piecewise linear functions: Algorithms and applications. Discr. & Comp. Geometry 4, 311–336 (1989)

Furnas, G.W.: Generalized fisheye views. SIGCHI Bull. 17, 16–23 (1986)

Gaertler, M.: Clustering. In: Brandes, U., Erlebach, T. (eds.) Network Analysis. LNCS. vol. 3418, pp. 178–215. Springer, Heidelberg (2005)

Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W. H. Freeman and Company (1979)

Görke, R., Gaertler, M., Wagner, D.: Lunarvis - Analytic Visualizations of Large Graphs. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 352–364. Springer, Heidelberg (2008)

Hachul, S., Jünger, M.: Drawing Large Graphs with a Potential-Field-Based Multilevel Algorithm. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 285–295. Springer, Heidelberg (2005)

Halldórsson, M., Radhakrishnan, J.: Greed is good: Approximating independent sets in sparse and bounded-degree graphs. Algorithmica 18, 145–163 (1997)

Harel, D., Koren, Y.: Graph Drawing by High-Dimensional Embedding. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol. 2528, pp. 207–219. Springer, Heidelberg (2002)

Holten, D., van Wijk, J.J.: Force-directed edge bundling for graph visualization. In: Proc. of the 11th Eurographics/IEEE-VGTC Symp. on Vis, pp. 983–990 (2009)

Koren, Y., Carmel, L., Harel, D.: Drawing huge graphs by algebraic multigrid optimization. Multiscale Modeling and Simulation 1, 645–673 (2003)

Mackaness, W.A., Beard, K.M.: Use of graph theory to support map generalization. Cartography and Geographic Information Science 20, 210–221 (1993)

Mackaness, W.A., Ruas, A., Sarjakoski, L.T. (eds.): Generalisation of Geographic Information. Cartographic Modelling and Applications. Elsevier B.V. (2007)

Misue, K., Eades, P., Lai, W., Sugiyama, K.: Layout adjustment and the mental map. Journal of Visual Languages & Computing 6(2), 183–210 (1995)

Openstreetmap database (2011),

Quigley, A., Eades, P.: Fade: Graph Drawing, Clustering, and Visual Abstraction. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 197–210. Springer, Heidelberg (2001)

Saalfeld, A.: Map Generalization as a Graph Drawing Problem. In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 444–451. Springer, Heidelberg (1995)

Sarkar, M., Brown, M.H.: Graphical fisheye views of graphs. In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, CHI 1992, pp. 83–91. ACM, New York (1992)

Telea, A., Ersoy, O.: Image-based edge bundles: Simplified visualization of large graphs. Computer Graphics Forum 29(3), 843–852 (2010)