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 an area of graph theory called “structural graph 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, assuming no background in graph theory.

The slides of the presentation are available here.

Speaker

Gwenaël Joret is professor at the Universite libre de Bruxelles (ULB).

Time and Place

Monday 04/12/2023 at 12:45pm in M.A.143

Registration

Participation is free, but registration is compulsory. Make sure to fill in this form.

References and Related Reading

TBA