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

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

Course 2-38-1, year 2023-2024.

Teachers: Luca Castelli Aleardi (École Polytechnique) and Éric Colin de Verdière (CNRS & Université Gustave Eiffel).

Other teachers not teaching this year: Vincent Cohen-Addad (Google Zürich), Arnaud de Mesmay (CNRS & Université Gustave Eiffel), and Vincent Pilaud (CNRS & École Polytechnique, responsible teacher for the course).

What's new?

NO LECTURE ON NOVEMBER 9: the lecture is postponed to November 16.

The final exam will take place on November 30, same time slot and location as the lectures. Please prepare two sets of sheets for your answers, one set for LCA's part and the other one for ÉCdV's part. The exam will be provided in English and French; answers can be provided either in English or in French. Printed course notes (slides, handout) and handwritten notes are allowed. No other written documentation, and no electronic devices, are allowed.

Second exercise sheet, due November 2. First exercise sheet, due October 12.

Practical information

When? First period, Thursdays, from 8:45 to 11:45, starting September 14. The tentative contents of the lectures is as follows:

  • Sep. 14: LCA (basics of planar graphs)
  • Sep. 21: LCA () and ÉCdV (basic algorithms for planar graphs, Chapter 3 of notes)
  • Sep. 28: LCA () and ÉCdV (more algorithms for planar graphs, Chapter 3 of notes)
  • Oct. 5: LCA () and ÉCdV (surface classification, Chapter 4 of notes)
  • Oct. 12: LCA () and ÉCdV (shortest loops, Chapter 5 of notes)
  • Oct. 19: LCA () and ÉCdV (shortest cut graphs, Chapter 5 of notes)
  • Oct. 26: NO LECTURE
  • Nov. 2: ÉCdV (universal covers, Chapter 6 of notes)
  • Nov. 9: NO LECTURE
  • Nov. 16: LCA () and ÉCdV (to be decided)
  • Nov. 30: Final exam

Where? Sophie Germain room 1002.

Language. Lectures 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. Questions can be raised in English or in French. Lecture notes will be available in English. The exam will be given in English, but a French translation will be provided upon prior request.

Evaluation. The evaluation is done with the final exam, which will take place on Friday November 23 or 30 (to be decided later), from 8:45 to 11:45, in room 1002 of the Sophie Germain building (usual schedule and room). Two exercises sheets will be proposed during the course period; if solved and given to the teacher (either a sheet written with a pen, or a LaTeX-formatted electronic version), 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 objects such as polytopes and surfaces, which appear in various contexts (optimization, discrete mathematics, topological graph theory).

Preliminary roadmap

  • Graphs drawn in the plane:
    • basics: combinatorial representations of planar graphs, topology, duality, Euler's formula;
    • Schnyder woods;
    • planarity testing and Tutte embedding;
    • efficient algorithms for planar graphs;
  • Graphs on surfaces:
    • classification theorem for surfaces up to homeomorphism;
    • topological algorithms for graphs on surfaces: shortest loops and systems of loops
    • Homotopy testing, and perhaps a few more things if time allows.

Course notes and slides

LCA's lectures: Lecture 1, Lecture 2, Lecture 3, Lecture 4, Lecture 5.

ÉCdV's lectures: course notes (only a subset will be treated)

Bibliography

  • The course notes (since no book covers all these topics).
  • Jesus A. De Loera, Jörg Rambau, and Francisco Santos. Triangulations: Structures for Algorithms and Applications, volume 25 of Algorithms and Computation in Mathematics. Springer Verlag, 2010.
  • Stefan Felsner. Geometric graphs and arrangements. Advanced Lectures in Mathematics. Friedr. Vieweg & Sohn, Wiesbaden, 2004. Some chapters from combinatorial geometry.
  • Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, 2001.
  • Günter M. Ziegler. Lectures on polytopes, volume 152 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1995.
  • Related courses have been taught elsewhere, with materials available online. See, e.g., Jeff Erickson and Francis Lazarus and Arnaud de Mesmay

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