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.

The project DISTANCIA focuses on the following research themes:

  • local-to-global properties of graphs occurring in MGT
  • median graphs and event structures
  • 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, identifying codes, and chi-boundedness
  • 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.