The goal of the project Algorithms and Complexity within and beyond Bounded Expansion was to develop a fine-grained theory of graph classes with bounded expansion (as well as other related notions of structural sparsity). The obtained

• structural and geometric characterizations

were used to

• find relationships between various properties of these graph classes,
• design efficient parameterized and approximation algorithms, and
• show complementary complexity results.

The project was funded in years 2020–2022 by the ERC-CZ grant LL2005 of the Ministry of Education of Czech Republic.

Project team:

• Zdeněk Dvořák (principal investigator)
• Robert Šámal (senior researcher)
• Jakub Pekárek (doctoral student)
• Abhiruk Lahiri (postdoc, since November 2021, on-line cooperation since 2020)
• Ben Moore (postdoc, since September 2021)

Publications:

• Z. Dvořák: On weighted sublinear separators, Journal of Graph Theory 100 (2022), 270–280.
• Z. Dvořák, L. Postle: On decidability of hyperbolicity, accepted to Combinatorica, 2022.
• Z. Dvořák, J. Pekárek, R. Šámal: Interval representation of balanced separators in graphs avoiding a minor, extended abstract, presented at Eurocomb 2021.
• Z. Dvořák, S. Norin: Weak diameter coloring of graphs on surfaces, arXiv.
• Z. Dvořák, S. Norin: Asymptotic dimension of intersection graphs, arXiv.
• Z. Dvorak, A. Lahiri, B. Moore: Square roots of nearly planar graphs, arXiv.
• A. Carbonero, P. Hompe, B. Moore, S. Spirkl: A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number, Journal of Combinatorial Theory, Series B 158 (2023), 63–69.
• Z. Dvořák, A. Lahiri: Approximation schemes for bounded distance problems on fractionally treewidth-fragile graphs, 29th Annual European Symposium on Algorithms (ESA 2021), Leibniz International Proceedings in Informatics (2021), 40:1–40:10.
• K. Gajjar, A.V. Jha, M. Kumar, A. Lahiri: Reconguring Shortest Paths in Graphs, 36th AAAI Conference on Articial Intelligence (2022).
• Z. Dvořák, J. Pekárek, T. Ueckerdt, Y. Yuditsky: Weak Coloring Numbers of Intersection Graphs, 38th International Symposium on Computational Geometry (SoCG 2022), Leibniz International Proceedings in Informatics (2022), 39:1–39:15.
• Z. Dvořák, D. Goncalves, A. Lahiri, T. Ueckerdt, J. Tan: On comparable box dimension, 38th International Symposium on Computational Geometry (SoCG 2022), Leibniz International Proceedings in Informatics (2022), 38:1–38:14.
• Z. Dvořák: Approximation metatheorems for classes with bounded expansion, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022), Leibniz International Proceedings in Informatics (2022), 22:1–22:17.
• Z. Dvořák: Representation of short distances in structurally sparse graphs, arXiv.