Résumé : In an effort to provide breadth instead of going deep into a single topic, the talk will cover two sets of geometric problems that are unrelated and suitable for a general audience interested in discrete mathematics and algorithms. In the first part I will explain variants of the barrier resilience problem, where the aim is to go from a source point to a target point in the plane visiting as few monitored regions as possible. The problem appears in sensor networks and in robotics, and its solution is related to vertex-disjoint paths/cycles in graphs. In the second part I will talk about crossing numbers of graphs and what we know about the crossing number of planar graphs with an additional edge.

 [Slides.pdf] [vidéo]

Dernière modification : Monday 18 March 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr