Institute of Theoretical Informatics, Algorithmics


Geometric Networks and their Visualization

DFG grants WO 758/4-1, 4-2, and 4-3
Group leader: PD Dr. Alexander Wolff

Project description

Geometric networks are the main tool to model flow of traffic, goods or information. They have applications in routing of railway systems, VLSI layout and the analysis of the world wide web. The networks are represented by geometric graphs whose objects (cities, persons, etc.) are points in a two- or more-dimensional space and whose relations (roads, blood relationship, etc.) are lines or curves that connect two points.

The project consists of two parts: (a) analysis and construction, and (b) visualization of geometric networks. In part (a) the focus is on networks where the distance of two geometric objects (like points or rectangles) within the network is bounded by a constant times their bee-line (i.e. Euclidean) distance. Such networks are called Euclidean spanners. They have many applications in distributed systems, communication network design, robotics, pattern recognition, data compression, and in biology. Part (b) deals with the question how networks with an underlying geometry (like subway networks) have to be distorted in the visualization process in order to improve their readability.

GeoNet is a research project funded by the Deutsche Forschungsgemeinschaft (DFG). It started in April 2003 and lasts for at most 5 years. Project leader is Dr. Alexander Wolff, the PhD students within the project are Marc Benkert, PD Dr. Martin Nöllenburg, and Dr. Ignaz Rutter. Besides doing research, various related topics are taught in lectures, seminars, and tutorials and master students are supervised.