Trial lecture: Paloma Thomé de Lima

Abstract:

"Graphs play a fundamental role in computer science. They are a useful tool to model and solve problems arising from various disciplines. Many such problems turn out to be computationally hard. However, graphs obtained from specific applications have inherent structural properties, that can be exploited in the design of efficient algorithms. Examples of such properties include the existence of special vertex orderings, decompositions and embeddings on surfaces.
 
In this talk, I will give a gentle introduction to this research area which is concerned with understanding how graph structure can be useful in algorithm design. I will discuss some recent developments that are relevant to my work, and outline some of the current challenges."

This is a trial lecture for a tenure track position in algorithms.