Invited Speakers
Oswin Aichholzer
Graz University of Technology
Graz
Eva Rotenberg
Technical University of Denmark
Kongens Lyngby (photo by Lars Svankjær)
Uli Wagner
Institute of Science and Technology Austria
Klosterneuburg
Abstracts
Oswin Aichholzer (Graz University of Technology)
Flips in Plane Graphs - Old Problems, New Results [slides]
Abstract: Reconfiguration is the process of changing a structure into another -
either through continuous motion or through discrete changes.
We concentrate on plane graphs and discrete reconfiguration steps of
bounded complexity, like exchanging one or two edge(s) of
the graph for one or two other edge(s), which is often called a flip.
The flip graph is defined as the graph having a vertex for
each configuration (in our case for each plane graph of a certain type)
and an edge for each flip between them.
Three questions are central: studying the connectivity of the flip
graph, its diameter, and the complexity of finding the shortest
flip sequence between two given configurations. Many classic and new
results are known, for example for flips in triangulations
or the transformation of plane spanning trees. We will give an overview
of these results and mention several (old and new) open
problems in this area, accompanied by recent developments for matchings,
trees, paths, and triangulations.
Eva Rotenberg (Technical University of Denmark)
How to Draw a Changing Graph
Abstract: A graph is planar if it can be drawn in the plane without its edges crossing (except at the endpoints). The algorithmic question of whether a graph admits a planar embedding can be decided in linear time [Hopcroft,Tarjan '74].
In this talk, we study the dynamic setting. Given a graph, consider that edges are inserted and deleted by an adversary. Can we efficiently update the answer to the yes/no question of whether the graph admits a planar embedding?
This talk presents a deterministic algorithm for updating the answer to said question; whether the graph is presently planar [Holm,R '20]. Our algorithm runs in an amortized time per update that is asymptotically cubic in the logarithm of the size of the graph; O(log³ n).
Curiously, our solution for maintaining that one bit of information goes via implicitly maintaining information about a feasible planar embedding of the present graph in the affirmative case (and a planar embedding of a planar subgraph, otherwise).
A natural next question is to study the notion of upward planarity, a restricted planar embedding of a directed graph, in which every directed edge must be embedded as a y-monotone curve. Here, we present some partial results [van der Hoog,Parada,R '24] and an open problem.
Uli Wagner (Institute of Science and Technology Austria)
Face Numbers of Polytopes and Levels in Arrangements
Abstract: Levels in arrangements (and the dual notion of k-sets) play a fundamental role in discrete and computational geometry and are a natural generalization of convex polytopes (which correspond to the 0-level). We will survey some classical results from the combinatorial theory of convex polytopes, including the Dehn–Sommerville Relations, McMullen’s Upper Bound Theorem, and the g-Theorem, due to Stanley and Billera–Lee, which completely characterizes the face numbers of simple polytopes. It is natural to wonder whether and to what extent this theory can be generalized to face numbers of levels in arrangements. We will discuss some steps in this direction, including both classical and new results, as well as various conjectures and open problems.
