### 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.