Seminars

Title: Elimination Distance to Bounded Degree on Planar Graphs
Link to the zoominar: univ-lille-fr.zoom.us/j/95419000064
Abstract:
What does it mean for a graph to almost be planar? Or to almost have bounded
degree?
On such simple graphs classes, some difficult algorithmic problems become
tractable.
Ideally, one would like to use (or adapt) existing algorithms for graphs that
are "almost" in such a simple class.

In this talk, I will discuss the notion of elimination distance to a class C, a
notion introduced by Bulian and Dawar (2016).
The goals of the talk are:
1) Define this notion, and discuss why it is relevant by presenting some
existing results.
2) Show that we can compute the elimination distance of a given planar graph to
the class of graph of degree at most d.
I.e. answer the question: "Is this graph close to a graph of bounded degree?"

The second part is the result of a collaboration with Alexandre Lindermayer and
Sebastian Siebertz.