Drawing Graphs: Geometric Aspects Beyond Planarity

• Applicant: Professor Dr. Alexander Wolff
• Subject Area: Mathematics ; Theoretical Computer Science
• Term: from 2019 to 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 405764128

• Final Report Year: 2024

Final Report 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 cubic 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 outerpaths, 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.

Link to the final report

https://oa.tib.eu/renate/handle/123456789/18841

Publications

• Line and Plane Cover Numbers Revisited. Lecture Notes in Computer Science, 409-415. Springer International Publishing.
  Biedl, Therese; Felsner, Stefan; Meijer, Henk & Wolff, Alexander
  
• Multi-level Steiner Trees. ACM Journal of Experimental Algorithmics, 24, 1-22.
  Ahmed, Reyan; Angelini, Patrizio; Sahneh, Faryad Darabi; Efrat, Alon; Glickenstein, David; Gronemann, Martin; Heinsohn, Niklas; Kobourov, Stephen G.; Spence, Richard; Watkins, Joseph & Wolff, Alexander
  
• Variants of the Segment Number of a Graph. Lecture Notes in Computer Science, 430-443. Springer International Publishing.
  Okamoto, Yoshio; Ravsky, Alexander & Wolff, Alexander
  
• Bundled Crossings Revisited. Journal of Graph Algorithms and Applications, 24(4), 621–655.
  Chaplick, Steven; Van Dijk, Thomas; Kryven, Myroslav; Park, Ji-won; Ravsky, Alexander & Wolff, Alexander
  
• The Segment Number: Algorithms and Universal Lower Bounds for Some Classes of Planar Graphs. Lecture Notes in Computer Science, 271-286. Springer International Publishing.
  Goeßmann, Ina; Klawitter, Jonathan; Klemz, Boris; Klesen, Felix; Kobourov, Stephen; Kryven, Myroslav; Wolff, Alexander & Zink, Johannes
  
• The Computational Complexity of the ChordLink Model. Journal of Graph Algorithms and Applications, 27(9), 759-767.
  Kindermann, Philipp; Sauer, Jan & Wolff, Alexander
  
• The Parametrized Complexity of the Segment Number. Lecture Notes in Computer Science, 97-113. Springer Nature Switzerland.
  Cornelsen, Sabine; Da Lozzo, Giordano; Grilli, Luca; Gupta, Siddharth; Kratochvíl, Jan & Wolff, Alexander
  
• Upward Planar Drawings with Three and More Slopes. Journal of Graph Algorithms and Applications, 27(2), 49-70.
  Klawitter, Jonathan & Zink, Johannes