Graph visualization

Graphs are not only a common tool for modelling and solving problems in computer science, but are also often used for visualizing data. Concrete drawings of graphs are understood also by non-experts; the representation of a link or a connection is intuitive. Moreover, methods for graph drawing can be used for visualizing real networks such as metro networks. We develop and investigate algorithms for creating readable drawings of graphs.

The literature describes many provably good algorithms for drawing graphs. Rarely, however, do these algorithms produce well-readable drawings. That is because it is often already hard to optimize only one desired criterion such as the number of bends or the number of edge crossings. This leads to other readability requirements not being fulfilled, perhaps because some edges are very long or some have many bends. It can, therefore, also make sense to do without solving partial problems optimally and rather balance several criteria against each other. A drawing can, for example, become better readable if there are slightly more crossings but all with large crossing angles.

Most existing algorithms for graph drawing work, furthermore, only on planar graphs, that is, graphs that can be drawn without crossings. Especially graphs based on real-world data are, however, usually not planar. If such graphs are large, which is not unusual, then single nodes or edges are hardly distinguishable in a drawing. There exist several approaches to draw such graphs: groups of edges are bundled or clusters of nodes are formed. So far, however, there is no method that always produces readable drawings.

Computational Geometry

How can we determine the nearest neighbor to each point in a set of points quickly? How can we efficiently calculate the average of two polygons? How can we find a target in an unknown environment?

These and many other questions are addressed by Computational Geometry, a subfield of computer science that began development in the 1970s and has since taken a stormy course. For good reason: On the one hand, dealing with geometric problems is inherently fascinating. Often, it is necessary to uncover hidden structural properties before an efficient algorithm can be developed. On the other hand, the questions studied have a direct relevance to real problems in application areas such as computer graphics, computer vision, geographic information systems, or robotics.

Rolf Klein, Preface to Algorithmische Geometrie: Grundlagen, Methoden Anwendungen, 2. Auflage, Springer. (in German)

Algorithmic Graph Theory

Algorithmic graph theory deals with the study of graphs and the development of efficient algorithms to solve graph-theoretical problems. A graph consists of nodes and edges that are connected to each other, and can be used to model relationships and networks in many application areas such as transportation, social sciences, biology, or computer networks.

In algorithmic graph theory, algorithms are developed that can be used to solve problems such as finding the shortest path between two nodes, determining connected components, or assigning nodes to clusters. The goal is to develop efficient algorithms that can solve these problems quickly and reliably, thus contributing to the optimization of processes and the improvement of applications.