Project 11: "(Geometric) graphs: Flip distances and crossing numbers"

This project is running since 2015.

Principal investigator: Oswin Aichholzer
Graz University of Technology, Austria.
Mentor for: Ross, Do; Andritsch, Lendl.

Associated scientist: Birgit Vogtenhuber (since 2017)
TU Graz, Austria.
Mentor for: Paul, Weinberger, Hammer; Parada, Vogel, Hüning.

DK Student

  • Third phase of the doctoral program:
  • Joachim Orthaber (Austria; since July 2022)
    Email: orthaber@ist.tugraz.at
    Mentors: Cesar Ceballos, Birgit Vogtenhuber.

  • Rosna Paul (India; since October 2019)
    Email: paul@tugraz.at
    Mentors: Bettina Klinz, Birgit Vogtenhuber.

  • Alexandra Weinberger (Austria; since October 2019)
    Email: weinberger@ist.tugraz.at
    Mentors: Bettina Klinz, Birgit Vogtenhuber.
  • Second phase of the doctoral program:
  • Irene Parada (Spain; August 2015–November 2019)
    Email: iparada@ist.tugraz.at
    Mentors: Bettina Klinz, Mark Parsons, Birgit Vogtenhuber.
    Thesis Title: "On straight-line and topological drawings of graphs in the plane".
    PhD Defense: November 13, 2019.
    Referees: O. Aichholzer, B. Richter (University of Waterloo), R. F. Monroy (Cinvestav).
    Examiners: O. Aichholzer, R. F. Monroy (Cinvestav).

Project description

Oswin Aichholzer's research interests include discrete and computational geometry, data structures and algorithms, combinatorial properties of geometric and topological graphs, and enumeration algorithms. On the algorithmic side his group is especially interested in combinatorial properties of triangulations and related data structures to obtain efficient algorithms for transforming or counting/ enumerating triangulations. This includes consideration of additional restrictions like bounds on the maximum face or vertex degrees. In the area of discrete geometry Aichholzer's group considers typical Erdős type problems on empty and non-empty convex polygons spanned by (colored and uncolored) point sets in the plane. On (geometric) graphs the focus lies on the minimum crossing number of complete graphs. Investigating the differences between geometric graphs (vertices are points in the Euclidean plane and edges are segments connecting two points) and general (topological) drawings of graphs has been proven very fruitful in the last few years and will play a central role in our project. Moreover, the relation of crossing minimal drawings to combinatorial structures, like k-edges and order types in the geometric case, or rotation systems in the topological setting, are of special interest.

Showcases for possible PhD themes can be found here.