Final Report of the DFG Project "Drawing Graphs: Geometric Aspects Beyond Planarity" (project number 654838)

Abstract

The aim of our project was to get a better understanding of the mathematical structures that correspond to the different ways of measuring the visual complexity of a drawing of a graph. Examples for such measures are the local crossing number, that is, the maximum number of crossings per edge, the slope number, that is, the number of different slopes in a crossing-free straight-line drawing, the segment number or the line cover number, that is, the number of straight-line segments or straight lines needed to cover a crossing-free straight-line drawing. For a graph, the measures are defined as the minimum over all drawings (of the corresponding type). The center of our studies became the measure segment number, which is known to be NP-hard to compute. In particular, we showed that there is a parameterized algorithm for computing the segment number of a given graph with respect to the several parameters; the natural parameter, the line cover number, and the vertex cover number. The latter proof was the technically most challenging. In a different work, we showed that it is ETR-complete to compute the segment number of a given graph, that is, the segment number of a graph can be expressed in terms of the existential theory of the reals, but its computation is at least as hard as every problem in the complexity class ETR. Moreover, we extended a result concerning the segment number of triconnected cu- bic planar graphs by showing that the segment number of every triconnected 4-regular planar graph with n vertices is at most n + 3, which is tight up to the additive constant. We have proved the first linear universal lower bounds for the segment number of out- erpaths, maximal outerplanar graphs, 2-trees, and planar 3-trees. This shows that the existing algorithms for these graph classes are in fact constant-factor approximation algorithms. For maximal outerpaths, our universal lower bound is best possible. Das Ziel unseres Projekts bestand darin, die mathematischen Strukturen besser zu ver- stehen, die den verschiedenen Möglichkeiten entsprechen, wie man die visuelle Kom- plexität der Zeichnung eines Graphen messen kann. Beispiele für solche Maße sind die lokale Kreuzungszahl, d.h. die maximale Anzahl von Kreuzungen pro Kante, die Steigungsanzahl, d.h. die Anzahl von verschiedenen Steigungen in einer geradlinigen und kreuzungsfreien Zeichnung, die Streckenzahl oder die Geradenüberdeckungszahl, d.h. die Anzahl von Strecken oder Geraden, die man braucht, um eine geradlinige kreuzungsfreie Zeichnung zu überdecken. Für Graphen werden die Maße als das Minimum über alle Zeichungen (des entsprechenden Typs) definiert. Ins Zentrum unserer Forschung ist das Maß Streckenzahl gerückt, von dem man schon wusste, dass es NP- schwer zu berechnen ist. Insbesondere konnten wir zeigen, dass es Fest-Parameter-Algorithmen für die Be- rechnung der Streckenzahl gibt; nämlich bezüglich des natürlichen Parameters, der Geradenüberdeckungszahl und der Knotenüberdeckungszahl. Letzteres war technisch am schwersten zu beweisen. In einer weiteren Arbeit haben wir gezeigt, dass es ETR-vollständig ist, die Stre- ckenzahl zu berechnen, d.h. die Streckenzahl kann einerseits mithilfe der existentiellen Theorie der reellen Zahlen ausgedrückt werden, andererseits ist ihre Berechnung min- destens so schwer wie die Lösung jedes anderen Problems in der Komplexitätsklasse ETR. Außerdem haben wir ein existierendes Resultat bezüglich der Streckenzahl von dreifach-zusammenhängenden kubischen planaren Graphen dahingehend erweitert, dass wir gezeigt haben, dass jeder dreifach-zusammenhängende 4-reguläre planaren Graph mit n Knoten eine Streckenzahl von höchstens n + 3 besitzt, was scharf ist bis auf die additive Konstante. Wir haben die ersten universellen unteren Schranken für die Streckenzahl von maximalen Außenpfaden, maximalen außenplanaren Graphen, 2-Bäumen und planaren 3-Bäumen bewiesen. Diese unteren Schranken zeigen, dass existierende Algorithmen für diese Graphklassen konstante Approximationsfaktoren be- sitzen. Für maximale Außenpfade ist unsere universelle untere Schranke bestmöglich.