GD2024 PhD School
Location
The PhD school takes place in the room
Lecture Hall 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 lecture hall GM3.
Program
| Monday, September 16 | |
|---|---|
| Time | Event |
| 09:00 — 12:00 | Reducing Connectivity Requirements: SPQR-Trees and Block-Cut-Trees |
| 09:00 — 10:30 | Lecture |
| 10:30 — 11:00 | Coffee Break |
| 11:00 — 12:00 | Exercises & Discussion |
| 12:00 — 14:00 | Individual Lunch Break |
| 14:00 — 17:00 | European Value Maps — From Theory to Application |
| 14:00 — 15:30 | Lecture |
| 15:30 — 16:00 | Coffee Break |
| 16:00 — 17:00 | Exercises & Discussion |
| Tuesday, September 17 | |
|---|---|
| Time | Event |
| 09:00 — 12:00 | Parameterized Algorithms and Few Crossings |
| 09:00 — 10:30 | Lecture |
| 10:30 — 11:00 | Coffee Break |
| 11:00 — 12:00 | Exercises & Discussion |
| 12:00 — 14:00 | Individual Lunch Break |
| 14:00 — 17:00 | Using SAT Solvers in Combinatorial Geometry and Graph Drawing |
| 14:00 — 15:30 | Lecture |
| 15:30 — 16:00 | Coffee Break |
| 16:00 — 17:00 | Exercises & Discussion |
| 19:00 — 21:00 | Welcome Reception, TUtheSky |
Lecturers
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 follow 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:
- What are SPQR-trees?
- How do they work?
- How can we use them?
Building upon that, we will have a closer look at the standard pipeline of reducing connectivity requirements for problems:
- Solve a problem for triangulated graphs.
- Extend the algorithm to 3-connected graphs.
- Use SPQR-trees to further extend it to 2-connected graphs.
- Use Block-Cut-trees to solve the problem on 1-connected graphs.
- 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.
Title:
European Value Maps — From Theory to Application
Abstract:
European Value Maps are conceptual maps representing human values across Europe. These maps enable the public to reflect on the diverse opinions held by European citizens. The ultimate goal is to promote acceptance and tolerance of different viewpoints, thereby reducing the opinion polarization that has become prevalent in our society.
In this lecture, you will learn about the methodology behind these maps, known as metaphoric maps, conceptual maps, or contact representations. These visualizations use polygonal regions to depict clusters of opinions and contacts among those regions, to depict the similarity between the opinion groups, leveraging the human familiarity with geographic maps.
We will walk through the steps of constructing these maps, starting with the data from the European Value Study. This includes data preparation, clustering, dimensionality reduction, and final geometric processing. Additionally, we will address the challenges that arise when considering data over time. Finally, we will discuss recent user studies on how these maps can influence opinion dynamics and their effectiveness in fostering open-mindedness among people.
Biography:
Tamara Mchedlidze is an Assistant Professor at the Department of Information and Computing Sciences of Utrecht University. Her research interests include Algorithms for Network Visualization, Visual Perception and Cognition and applications of network visualization in Digital Humanities. Before joining Utrecht University in 2020, Tamara was a postdoc at Karlsruhe Institute of Technology. She received her doctorate in Applied Mathematics from National Technical University of Athens in 2012, during which she was a Visiting DAAD Scholar at the Department of Informatics at Tübingen University.
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:
- 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.
- 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.
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.
Acknowledgments
The GD2024 PhD School acknowledges support from the Austrian Science Fund (FWF Project 10.55776/Y1329), which contributed to the interdisciplinary aspects of tutorials on topics intersecting parameterized complexity and artificial intelligence.
The GD2024 PhD School is a partner event of the LogiCS@TUWien Marie Skłodowska-Curie COFUND doctoral training programme.
