SFB TRR 161 TP B 02 Adaptive Network Visualization


We plan to design adaptive network layout algorithms and to assess their response behavior quantitatively through experimental algorithmics.The graph-drawing algorithms used in network information visualization are typically variants of the so-called spring embedder. A prime reason other than the intuitive physical analogy is that this class is especially versatile and adaptable.& However, the methods in this class are also known to be notoriously difficult to tune and steer.We will focus on a particular class of force-directed graph-drawing algorithms, which has proven to be practical, and for which we have extensive qualitative and quantitative experience : the stress-minimization variant of multidimensional scaling.& It is one of the most versatile methods for network visualization layout, much less ad-hoc than other force-directed layout methods, and there is plenty of opportunity for comparison with techniques and implementations from the domain of statistical data analysis.& The overall goal of this project will be addressed by identifying expressive layout features and the means to parametrize and control them precisely within this layout approach.Concretely, we will consider the following more detailed research questions:

    What are appropriate means of adaptation in network information visualization? Adaptations can be motivated by data intrinsic (e.g., graph invariants) or extrinsic (e.g., geographic coordinates) to the network, or by presentation conditions such as user interaction or display environment.Can we make reliable quantitative predictions about the relation between adaptations and layout effects? Visualizations that are adaptive to& presentation environment, level-of-detail, or user interaction require precise and predictable instantiation and parametrization of layout algorithms. Similarly, controlled user studies require quantitative means to assess model bias, which are thus prerequisite for future experiments on cognitive layout effectiveness.Which experiment-design techniques from other disciplines can be adopted to improve the study of algorithm behavior? As a byproduct of the visualization-oriented research goal, we hope to contribute to methodological developments in the area of experimental algorithmics.Can we improve the parametrization of graph layout algorithms? Depending on intermediate outcomes, we expect to continue this project either by broadening its scope to include more general adaptations and other layout algorithms, or by refining the analysis in terms of sensitivity and controllability.

The outcome of this research is supposed to allow for adaptive network visualization techniques that are robust with respect to input characteristics and display environments, and that support interactive control of layout features with well-understood response curves.These are prerequisites for controlled user studies and would facilitate future studies of the effects of adaptation on the perception of network properties.

  • WG Brandes (Algorithmics)
  • Zukunftskolleg
  Schäfer, Peter (2024): Polyline Simplification using the Fréchet Distance - Algorithms and Engineering

Polyline Simplification using the Fréchet Distance - Algorithms and Engineering


Polylines are used to represent curves by a sequence of straight segments. Simplification asks for a subsequence that is close to the original according to some similarity measure, and a given threshold value 𝜀. Polyline simplification is a building block for a variety of applications in computational geometry: drawing maps, or other vector graphics on various levels of detail, data compression, analysis of time series, robotics, bio-informatics and many more.

A commonly used similarity measure is the Hausdorff distance that operates on point sets. In contrast, the Fréchet distance accounts for the course of a polyline. It is, therefore, considered to be more useful – but also more challenging in terms of computational complexity. Various applications and variations of the Fréchet distance have been studied over the last decades.

In this work, we explore the use of the Fréchet distance for polyline simplification from four different angles. First of all, we present a new algorithm that significantly improves a long-standing running-time boundary of an existing algorithm. We explore theoretical aspects and we demonstrate its practical usefulness. Next, we propose two new variations on existing problem settings: we call them gradual simplification, and consistent simplification of polyline bundles. We

believe these new problem settings to be interesting in their own. We analyze their characteristics, design efficient algorithms and, again, demonstrate their applicability. Lastly, we adapt an existing algorithm to a new application field, improving it in the process. We provide a new tool for the analysis of eye-tracking data, and, hopefully, more application fields.

In addition to analyzing theoretical properties of algorithms, we always aim to prove the practical usefulness of our approaches. We recognize that oftentimes, deeper understanding of problems can not be gained from theoretical analysis alone. For this reason, we build prototypes implementing our new algorithms, and evaluate them on real-world data. The insights gained from these experiments help us in turn to improve the algorithmic designs.

Origin (projects)

  van Garderen, Mereke (2018): Pictures of the Past : Visualization and visual analysis in archaeological context

Pictures of the Past : Visualization and visual analysis in archaeological context


Data visualization, the main topic of this dissertation, is the science concerned with the design and creation of visual representations intended to convey information and facilitate understanding. In a scientific context, the data to be visualized are typically research results, which can originate from any discipline. The main challenges in data visualization are to find visual representations which (1) are as accurate as possible, (2) can be understood quickly and well by viewers, and (3) can be produced automatically and efficiently. The latter is especially important when large or dynamic data sets are involved. This dissertation is focused on addressing these challenges for a particular application domain: the visualization of archaeological data. We identify general properties that often characterize archaeological data and discuss a variety of visualization methods suitable for data with these properties. For existing methods from the area of mathematics and computer science, we explain how they can be applied – either directly or with some adaptations – in the context of archaeology. We also introduce new approaches, tailored to various archaeological applications. Case studies and real archaeological data sets are used to demonstrate the use of these approaches in practical applications. However, because of our focus on general data properties rather than specific data sets, the methods presented in this dissertation are in fact widely applicable beyond the field of archaeology as well.

Origin (projects)

Funding sources
Name Finanzierungstyp Kategorie Project no.
SFB third-party funds research funding program 632/15
Further information
Period: 01.07.2015 – 30.06.2019