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.

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.

Project description (pdf-file)

Research interests of Oswin Aichholzer include discrete and computational geometry, data structures and algorithms, combinatorial properties of geometric and topological graphs, and enumeration algorithms. On the algorithmic side he is especially interested in combinatorial properties of triangulations and related data structures, and aims to obtain efficient algorithms for transforming or enumerating triangulations. This includes consideration of additional restrictions like bounds on the maximum face or vertex degrees. In the area of discrete geometry he is interested in typical Erdos 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 plays an important role in Aichholzer's research. Furthermore, 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.