Ivor  van der Hoog

Project title: Computing Graph Properties of Real-world Graphs

Host Institution: Technical University of Denmark (DTU)

Host Supervisor: Dr. Eva Rotenberg

Co-host Institution: Eindhoven University of Technology (TU/e)

Co-host Supervisor: Prof. Bettina Speckmann

Summary project: Computing graph properties is one of the most-studied topics in theoretical computer science. Graphs are a mathematical abstraction of day-to-day concepts such as roads, chemical structures, or networks. Computing graph
properties hence has many applications from applied science, to industry. There has been a recent surge in techniques for analysing real-world (planar, Euclidean, or Unit) graphs. These advancements show that these restricted settings circumvent many quadratic lower bounds for computing graph properties. The goal of this project is to expand upon these recent improvements and study the following question:
“can algorithms for computing graph properties be made more efficient when assuming real-world settings (beating lower bounds for general graphs)?”