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 , 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

Actions (login required)

View Item View Item