Structural Sparseness: Theory and Practice

Sparseness is undoubtedly one of the most useful graph properties for algorithm design: whether it is planarity for approximation schemes, bounded treewidth for dynamic programming, or excluded minors for parametrised algorithms. But do these algorithms actually translate into usable programs or are they simply 'galactic algorithms' of theoretical interest only?

In this talk I invite you to critically examine the issue of practicality and argue why theoreticians should care about it. I will particularly focus on bounded expansion/nowhere dense classes and try to convince you that a practical algorithmic toolkit exploiting those properties is feasible. Along the way, I will highlight some of my recent experiences in the intersection of practical algorithms and structural sparseness.