The Graph Sparsity Theory of Nešetřil and Ossona de Mendez is a highly active and rapidly developing topic in combinatorics and graph theory, withapplications in many areas including algorithmic graph theory, complexity theory, and property testing. A recent focus of structural and algorithmicgraph theory has been to extend the graph sparsity theory to dense graph classes. The proposed project aims at introducing novel ways andmethods of addressing this goal. This will be done along the following two interconnected research lines:
- first, by advancing the recently emerging and fast developing theory of graph width and depth parameters through a general framework based ongraph measures and an in-depth analysis of known and novel graph parameters;
- second, by developing a biparametric theory of hereditary graph classes in which some parameter is bounded by a function of another one, withthe goal of identifying nontrivial structural and algorithmic implications.
Our approach is complementary to the theory of graph classes with bounded flip-width developed recently by Toruńczyk and will lead to an improvedunderstanding of the boundaries of tractability for maximum independent set and several other practically relevant graph optimization problems.