### 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*: Andritsch, Lendl.

Associated scientist: Birgit Vogtenhuber (since 2017)

TU Graz, Austria.

*Mentor for*: Lindorfer, Parada, Vogel, Hüning.

### DK Student

**Second phase of the doctoral program:****Irene de Parada**(Spain; since August 2015)

*Email*: iparada@ist.tugraz.at

*Mentors*: Bettina Klinz, Mark Parsons, Birgit Vogtenhuber.

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