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

- 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.