Graph Drawing and Geometric Representations

Visualization of graphs and networks has become crucial in many real world applications, especially nowadays when large scale networks need to be displayed in an easy-to-grasp way. Deep theoretical results in structural graph theory lead to design of fast algorithms to achieve this, while, at the same time, motivation stemming from applications strongly influences basic research in graph theory and discrete mathematics. One can hardly find a more prominent example of crossfertilization between theory and practical applications. The historically oldest concept of graph visualization is the notion of planarity. The famous map colouring problem took almost 100 years to be finally resolved by a computer-aided proof [Appel and Haken 1976, Robertson et al. 1996]. Kuratowski’s structural characterization of planar graphs by forbidden minors [1930] marks the beginning of modern graph theory, the first linear-time planarity testing algorithm of Hopcroft-Tarjan [1974] secured them (both planar graphs as well as Hopcroft and Tarjan) eternal placement in the hall of fame of theoretical computer science. The long line of research on planar graphs has generated a broad basis of both structural and algorithmic results. Nevertheless, interest in planarity remains vital and interesting connections and results continue to emerge: Excluded planar minors play an exceptional role in structural graph theory, recent algorithmic results treat constrained planarity problems, surprising theorems on intersection representations of planar graphs have been proved. Still, many old problems remain open, and many new ones are emerging.

The aims of this CRP are to attack well known hard problems both from structural and algorithmic points of view. The research will be concentrated around planarity issues, will go beyond planarity and explore geometric representations of graphs. Given the dynamics of the field we expect to encounter and identify new frontiers and new research directions. Since visualization of graphs is motivated by practical applications, a key ingredient of the project is cross-fertilization of theory and applications.

The group in Würzburg is particularly interested in the problem of computing the layout of complex networks under angular restrictions. We refer to this problem as angular schematization and subsume under it also the combined effort of network construction and layout. It is striking that edge directions are being restricted in networks of very different nature and that these networks are constructed in very different communities: graph drawing, information visualization, geographic information science, computational geometry, VLSI layout, and underground mining.

In some of these communities (such as graph drawing or VLSI layout), rectilinear connections have a long history, but recently octilinear connections have moved into the spotlight, bringing with them completely new problems and challenges. In other fields of application such as underground mining, it is not the number of slopes that is restricted, but there is an upper bound in the maximum slope.

As a first step, we are organizing an interdisciplinary Dagstuhl seminar (Nov. 14–19, 2010) on the topic. This meeting will ignite the discussion with researchers from application areas and will lay the foundations for further cooperation within the work package.

» Final Report