DS07 - Société de l'information et de la communication

Metric graph theory – DISTANCIA

Submission summary

This proposal is concerned with theoretical foundations and applications of the metric graph theory that studies the structure and algorithmics of graph classes whose metric satisfies the main properties of classical metric geometries.

Such applications can be found in many different areas. The hub labelling problem in road networks can be directly applied to car navigation applications. Understanding key structural properties of large-scale data networks is crucial for analyzing and optimizing their performance, as well as improving their reliability and security. Metric graph theory was also indispensable in solving some open questions in concurrency and learning theory in computer science and geometric group theory in mathematics. Median graphs play a vital role in geometric group theory (for example, in the recent solution of the famous Virtual Haken Conjecture). They are also the domains of event structures of Winskel, one of the basic abstract models of concurrency. This correspondence was useful to disprove Rozoy-Thiagarajan and Thiagarajan's conjectures about nice labelings and regular labelings. A remarkable appearance of modular graphs occurred in classifying the complexity of the so-called $0$--extension problem, a combinatorial optimization problem generalizing the minimum cut problem and having applications in computer vision. Many classical algorithmic problems concern distances: shortest path, center and diameter, Voronoi diagrams, TSP, clustering, etc. Algorithmic and combinatorial problems related to distances occur in data analysis. Low-distortion embeddings were the founding tools in metric methods on which are based several approximation algorithms for NP-hard problems. Finally, in the distributed setting, an important problem is that of designing compact data structures allowing very fast computation of inter-node distances or routing along shortest or almost shortest paths. Besides computer science and mathematics, applications of structures involving distances can be found in archeology, computational biology, statistics, data analysis, etc.

With this proposal, we aim to participate at the elaboration of this new domain of Metric Graph Theory, which requires experts and knowledge in combinatorics (graphs, matroids), geometry, and algorithms. This expertise is distributed over the members of the consortium and a part of the success of our project it will be to share these knowledges among all the members of the consortium. This way we will create a strong group in France on graphs and metrics. The project aims at investigating several strongly interconnected research questions from metric graph theory and algorithmics of finite metric spaces. We will try to make substantial contributions to combinatorial, algorithmic, geometric, and topological structure of graphs occurring in metric graph theory and of their associated cell complexes by developing and exploiting theory for common structures and structural similarities that occur in problems from diverse areas. We hope to use this increased knowledge for solving questions in computer science (concurrency and computational learning theory), discrete mathematics, and combinatorial optimization. We would also like to develop algorithms for distance problems related to data analysis, network analysis, distributed computing, and seriation.

The project focus on two main subjects "Structure in metric graph theory" and "Algorithms in metric graph theory'', consisting of ten strongly interconnected research themes :

S1. Local-to-global characterizations
S2. Median graphs and event structures
S3. Lopsided sets and sample compression
S4. Matroidal structures
S5. Isometric and low distortion embeddings
S6. Packing and covering with balls, identifying codes, and $\chi$-boundedness

A1. Algorithmic aspects of hyperbolic graphs
A2. Algorithms for graph classes from MGT
A3. Finite metric spaces: approximation and realization
A4. Seriation and classification.

Project coordinator

Monsieur Victor Chepoi (Laboratoire d'informatique Fondamentale de Marseille)

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.


IRIF Institut de Recherche en Informatique Fondamentale
LIF Laboratoire d'informatique Fondamentale de Marseille

Help of the ANR 320,410 euros
Beginning and duration of the scientific project: September 2017 - 48 Months

Useful links

Explorez notre base de projets financés



ANR makes available its datasets on funded projects, click here to find more.

Sign up for the latest news:
Subscribe to our newsletter