Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

This is an old revision of the document!


Algorithmique et combinatoire des graphes géométriques / Algorithms and combinatorics for geometric graphs (24h)

Course 2-38-1, year 2019-2020.

Teachers: Vincent Cohen-Addad (CNRS & Université Paris 6 Pierre et Marie Curie) and Éric Colin de Verdière (CNRS & Université Paris-Est Marne-la-Vallée).

Teacher in charge of the course, not teaching this year: Vincent Pilaud (CNRS & École Polytechnique).

What's new?

The course starts on Wednesday, September 11.

The final exam will be on November 13 or 20, usual time and room.

Practical information

Where? Sophie Germain building, room 1013.

When? First period, Wednesdays, 12:45-15:45. Typically, each 3-hour lecture will be split into two parts, each taught by one of the teachers.

Language. Lessons will be given in French by default, or in English upon request of at least three persons who do not understand French, and if nobody objects. Lecture notes will be available in English. The exam will be translated if needed.

Evaluation. The evaluation is done with the final exam. Three exercises sheets will be proposed during the course period; if solved, they will give some extra credit for the final grade.

Prerequisites. None.

Main theme

Algorithms and combinatorics for graphs are a major theme in computer science. In this course, we study various aspects of this theme in the case of graphs arising in geometric settings. Examples include planar graphs (of course), graphs drawn without crossings on topological surfaces, and graphs of polytopes and other combinatorial structures. The course is therefore at the frontier of graph algorithms, combinatorics, and computational geometry.

Following this course is a good opportunity

  • to see some relatively standard tools in algorithms and combinatorics applied in geometric settings,
  • leading to results at the edge of current research, and
  • to learn about some fundamental concepts which appear in various contexts (optimization, discrete mathematics, topological graph theory).

Preliminary roadmap

The two parts of the course are relatively independent, except for the basics taught by ECV.

ECV's part:

  • Graphs drawn in the plane:
    • basics: combinatorial representations of planar graphs, topology, duality, Euler's formula;
    • planarity test and graph drawing algorithms;
    • efficient exact algorithms for planar graphs: minimum spanning tree, vertex coloring, minimum (s,t)-cut.
  • Graphs drawn on surfaces:
    • Classification of surfaces
    • Computing with cut locus: shortest non-contractible and non-separating closed curve; shortest cut graph
    • Deciding homotopy with universal covers
    • If time: minimum (s,t)-cut on surfaces, or tightening curves on surfaces

VCA's part:

  • Balanced Separators of planar graphs, r-division, and algorithmic applications (e.g.: approximation algorithm for the independent set problem).
  • The power of local search in planar graphs: a paradigm to solve various optimization problems (independent set, dominating set, vertex cover). Generalization to facility location.
  • The power of local search for clustering problems:
    • facility location in low-dimensional Euclidean space, decomposition of Voronoi diagrams.
    • facility location in general metrics.
  • Metric embeddings and their algorithm applications: Johnson-Lindenstrauss; metric embedding into tree metrics.
  • Locality sensitive hashing and nearest neighbor search.

Course notes

A superset of ECV's notes can be found here.

Bibliography

  • The course notes (since no book covers all these topics).
  • Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, 2001.
  • more to come for VCA's course; stay tuned.

Relevant courses

 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA