How to decompose planar graphs?

Speaker: Gwen Joret

Room: B508

Date: 17/05/2024 14:00

Abstract:

Planar graphs, graphs that can be drawn in the plane without edge crossings, are among the most natural and ubiquitous kinds of graphs. They appear in numerous real-life applications (think of road networks for instance). They also play a central role in structural graph theory, and in particular in graph minor theory. For these reasons, it is interesting to study the *structure* of planar graphs: How can we decompose them into basic building blocks that are "simple"? What kind of tricks can we use to solve optimization problems on planar graphs? This is the topic of this talk. I will start with  classic tools from the 1970s and 1980s such as the Lipton-Tarjan separators and Baker's decomposition technique, and then move on to some very recent results in the area obtained in the last 2-3 years.  While planar graphs are as old as graph theory---they were already studied in the 1850s due to the 4 Color Conjecture---they are not yet fully understood, researchers are still discovering hidden  structures and new theorems about these graphs today. This is an exciting research area to work in at the moment. In my talk I will give a gentle introduction to the area.