Welcome to the webpage of the ANR-funded project DISTANCIA (Metric Graph Theory, ANR-17-CE40-0015). The project started in October 2017 and will finish in September 2021.
Metric graph theory (MGT) investigates graphs from metric point of view. The central subject of this theory is the investigation and characterization of graph classes and related cell (cubical and simplicial) complexes, whose metric satisfies the main properties of classical metric geometries. Surprisingly, some classes of graphs from MGT occur also (under different guises) in geometric group theory, concurrency, combinatorics, discrete geometry, combinatorial optimization, and learning theory. We will also investigate algorithmic problems related with distances.
The project DISTANCIA focuses on the following research themes:
- local-to-global aspects of classes of graphs from MGT
- median graphs/CAT(0) cube complexes and event structures/1-safe Petri nets
- ample classes and sample compression
- metric aspects of matroidal structures (basis graphs and tope graphs)
- partial cubes and isometric/low distortion embeddings
- covering and packing with balls and chi-boundedness, identifying codes
- algorithmic aspects of hyperbolic graphs
- algorithms for distance problems
- finite metric spaces: approximation and realization
- seriation and classification.
These themes are grouped in two main subjects: “Structure in metric graph theory” and “Algorithms in metric graph theory”. More details on the project can be found here.