Location

The PhD school takes place in the room

GM3 of TU Wien
Getreidemarkt 9
1060 Vienna,

which is located on the 2nd floor of the building BA of Campus Getreidemarkt (same building as the main conference venue). On the venue page, you can find a more detailed description of how to reach the building.

The location is accessible by wheelchair and the registration and coffee breaks for the PhD school are located in front of the room GM3.

Program

Event Speaker
Sep. 16, 09:00 - 12:00 Philipp Kindermann
Sep. 16, 14:00 - 17:00 Tamara Mchedlidze
Sep. 17, 09:00 - 12:00 Thekla Hamm
Sep. 17, 14:00 - 17:00 Manfred Scheucher
Each session contains two parts and a coffee break  

Lecturers

Philipp Kindermann

Trier University, Germany

Title:

Reducing connectivity requirements: SPQR-trees and Block-Cut-trees

Abstract:

When trying to solve an open problem for planar graphs, one often starts with considering only triangulated or 3-connected graphs. But at some point, everybody will hear the dreaded question: "Can we extend this to biconnected graphs with SPQR-trees?"

SPQR-trees are by their very nature intimidating. Without experience one can quickly become lost while trying to following arguments of more senior researchers that are used to them. In this lecture, we want to overcome the fear of SPQR-trees. We will investigate the following questions:

  1. What are SPQR-trees?
  2. How do they work?
  3. How can we use them?

Building upon that, we will have a closer look at the standard pipeline of reducing connectivity requirements for problems:

  1. Solve a problem for triangulated graphs.
  2. Extend the algorithm to 3-connected graphs.
  3. Use SPQR-trees to further extend it to 2-connected graphs.
  4. Use Block-Cut-trees to solve the problem on 1-connected graphs.
  5. Consider how to handle disconnected graphs.

Biography:

Philipp Kindermann is a junior professor for algorithms at Trier University, Germany. He received his BSc, MSc and PhD in Computer Science from University of Würzburg, Germany. He has been a guest professor at University of Passau in 2020. He is interested in everything involving graph drawing, both from the theoretical and from the practical side, and its related fields like algorithmic graph theory, algorithm engineering, computational geometry, and information visualisation. He was involved in the organization of several contests in the last few years: the Graph Drawing Contest, the Computational Geometry Challenge, and the Parameterized Algorithms and Computational Experiments Challenge.


Tamara Mchedlidze

Utrecht University, The Netherlands

Title:

tba

Abstract:

tba

Biography:

tba


Thekla Hamm

TU Eindhoven, The Netherlands

Title:

Parameterized Algorithms and Few Crossings

Abstract:

Crossings are among the most classically considered features of drawings. The most fundamental computational problem in this context is the crossing number problem which is known to be computationally difficult (even to approximate). Parameterized complexity theory provides a general framework to obtain a more detailed understanding of and find ways to circumvent such hardness - not only for this problem. Moreover, the crossing number can also be viewed as a measure of how far a graph is from being planar, making it a potentially interesting parameter for the design of parameterized algorithms for other graph problems. In this tutorial we will take a look at both of these aspects:

  1. Overview over some parameterized questions that have been asked for graph drawing problems in which the number of crossings are restricted in some way and demonstration of famous techniques from parameterized complexity theory, such as Courcelle's theorem and bidimensionality, to attack them.
  2. Light exploration of crossing number for the analysis of the parameterized complexity of other problems. Prior knowledge of parameterized complexity theory will not be required, but in that case this tutorial will not substitute a thorough introduction but be more of a crash-course.

Biography:

Thekla Hamm's research lies mostly in the area of parameterized complexity theory and its application to problems involving graph structure. Within the area of graph drawing, this has led to a line of research centering around parameterized algorithms for drawing extension with crossing restrictions. From September 2024, Thekla Hamm is an assistant professor in the algorithms cluster at TU Eindhoven. Before that, she obtained her PhD in 2022 under the supervision of Robert Ganian at TU Wien and worked as a postdoc at Utrecht University.


Manfred Scheucher

TU Berlin, Germany

Title:

Using SAT solvers in Combinatorial Geometry and Graph Drawing

Abstract:

The area of SAT solving has seen tremendous progress over the last years and many problems that seemed to be out of reach a decade ago can now be handled routinely [1]. In this session we will discuss how intricate problems from combinatorial geometry and graph drawing can be tackled using SAT solvers and related techniques.

First, we will discuss how mathematical problems can encoded as propositional logic formula over a finite set of Boolean variables (Boolean satisfiability problem). While most problems from combinatorics come with a natural encoding that is moderately suited for computer investigations, it is often a non-trivial task to attack problems from geometry or graph drawing. A naive encoding may come with non-linear constraints over real-valued variables, and solving might be ETR-hard, where ETR (existential theory of the reals) is a complexity class between NP and PSPACE. However, in the last decades it turned out to be a promising approach to tackle a related problem with slightly relaxed constraints instead. For example, problems on points sets, geometric graphs, or line arrangement can be investigated via pseudo-configurations of points or pseudoline arrangements, which come with a polynomial sized axiom system over Boolean variables. Even though this approaches is sometimes sufficient to address long-standing notoriously hard problems, such relaxations may introduce configurations which are not representative for the original setting. And it is not at all surprising that deciding representativity (a.k.a. realizability) is often ETR-hard, such as the original problem.

[1] https://satcompetition.github.io/2024/

Biography:

Manfred Scheucher did his Bachelor and Master studies at TU Graz, his PhD with Stefan Felsner at the TU Berlin, and is now postdoctoral researcher and principal investigator of a DFG project at TU Berlin. The focus of his research lies in the interface of theoretical computer science and discrete mathematics, in particular, combinatorial geometry. His primary objective is to tackle fundamental mathematical problems by combining classic proving techniques with automated reasoning tools, in particular, SAT solvers, computer algebra systems, and large computing clusters.