Aktualności / News > SONATA BIS
SONATA BIS
Key information:
Project title: From dense graphs to sparse ones and back again
Duration: 07.04.2025 - 06.04.2030
Funding: National Science Centre (NCN)
Team:
- Paweł Rzążewski, principal investigator
- join!
Main objectives:
The notion of sparse graphs has been one of the central concepts in structural and algorithmic graph theory in past few decades. There are many reasonable definitions of "sparse," but in general classes of sparse graphs are considered to be well-understood. They often admit some strong structural properties which allow us to, e.g., bound the chromatic number. In many cases these properties can also be exploited algorithmically.
However, it turns out that even among classes of dense graphs we can find many examples that are well-structured. Intuitively speaking, we will be interested in classes of graphs that "only pretend to be dense." Slightly more formally, there are classes of (possibly dense) graphs that admit some sparse underlying structure. There are many ways of defining such structurally sparse classes, e.g., via discrete geometry, as intersection graphs of geometric objects, using matroid theory etc.
In this project we will be mostly interested in classes defined by:
* forbidding certain patterns, especially as induced minors,
* bounding certain width parameters, especially related to structured tree-like decompositions.
Moreover, we are also going to look at classes of graphs that "only pretend to be sparse." More specifically, we are going to investigate (possibly sparse) graphs with a total order on vertices. The total order relation is dense, but still not very complicated. Due to the first property, even very simple families of graphs (say, matchings) have quite rich structure in the ordered world. Due to the second property, we might still hope for some interesting structural and algorithmic results.
We aim to look at ordered graphs from two perspectives. First, we want to conduct a systematic study of structural and algorithmic properties of classes of ordered graphs defined by forbidding certain (ordered) induced subgraphs. Such investigations in the unordered setting are in the core of the modern structural and algorithmic graph theory.
Second, we want to investigate order-preserving homomorphisms of ordered graphs, and explore their combinatorial and computational properties. We attempt to build a theory similar to the one of homomorphisms of unordered graphs.
Summing up, the proposed project has the following high-level goals.
Goal 1. Explore structural and algorithmic properties of classes of graphs defined by forbidden induced minor or by bounding width parameters related to structured tree-like decompositions.
Goal 2a. Initiate and conduct a systematic study on structural and algorithmic properties of ordered graph classes defined by forbidding certain induced subgraphs.
Goal 2b. Initiate the study of the theory of order-preserving homomorphisms of ordered graphs.
However, it turns out that even among classes of dense graphs we can find many examples that are well-structured. Intuitively speaking, we will be interested in classes of graphs that "only pretend to be dense." Slightly more formally, there are classes of (possibly dense) graphs that admit some sparse underlying structure. There are many ways of defining such structurally sparse classes, e.g., via discrete geometry, as intersection graphs of geometric objects, using matroid theory etc.
In this project we will be mostly interested in classes defined by:
* forbidding certain patterns, especially as induced minors,
* bounding certain width parameters, especially related to structured tree-like decompositions.
Moreover, we are also going to look at classes of graphs that "only pretend to be sparse." More specifically, we are going to investigate (possibly sparse) graphs with a total order on vertices. The total order relation is dense, but still not very complicated. Due to the first property, even very simple families of graphs (say, matchings) have quite rich structure in the ordered world. Due to the second property, we might still hope for some interesting structural and algorithmic results.
We aim to look at ordered graphs from two perspectives. First, we want to conduct a systematic study of structural and algorithmic properties of classes of ordered graphs defined by forbidding certain (ordered) induced subgraphs. Such investigations in the unordered setting are in the core of the modern structural and algorithmic graph theory.
Second, we want to investigate order-preserving homomorphisms of ordered graphs, and explore their combinatorial and computational properties. We attempt to build a theory similar to the one of homomorphisms of unordered graphs.
Summing up, the proposed project has the following high-level goals.
Goal 1. Explore structural and algorithmic properties of classes of graphs defined by forbidden induced minor or by bounding width parameters related to structured tree-like decompositions.
Goal 2a. Initiate and conduct a systematic study on structural and algorithmic properties of ordered graph classes defined by forbidding certain induced subgraphs.
Goal 2b. Initiate the study of the theory of order-preserving homomorphisms of ordered graphs.