The last lecture was November 13. There are no lectures on November 20 and November 27.

Final exam will take place on December 4, usual room (1002 of Sophie Germain building). The exam will be in two parts, one for each teacher. Please prepare two sets of answer sheets, one for each part. Allowed documents: the course notes and handwritten documents. No electronic devices. The exam will have a French and an English version; answers can be given in either language.

First homework (optional): homework 1 (due on november 6th, before 9am)

Second homework (optional) homework 2 (due on November 26 AoE, November 28 AoE, by e-mail at arnaud.de-mesmay@univ-eiffel.fr). Solution.

When? First period, Thursdays, from 8:45 to 11:45, starting September 18.

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. The exam may be provided both in English and in French if requested.

All the material is in English (lectures notes, slides, …)

Evaluation. The evaluation is done with the final exam. Two exercises sheets (homeworks) 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. All required notions will be introduced during the course.

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).

• Graphs drawn in the plane:
  • basics: combinatorial representations of planar graphs, topology, duality, Euler's formula (Lecture 1);
  • planarity testing and Tutte embedding (Lecture 1);
  • Crossing Lemma, Hanani-Tutte theorem and a slow polynomial-time algorithm for planarity-testing (Lecture 2);
  • Planar grid drawings: Canonical Orderings and Schnyder woods (Lecture 3);
  • efficient algorithms for planar graphs (Lecture 4);
  • Schnyder woods for 3-connected graphs and orthogonal surfaces (Lecture 5);
  • Planar separators and applications (Lecture 7);
• Graphs on surfaces:
  • classification theorem for surfaces up to homeomorphism (Lecture 6);
  • topological algorithms for graphs on surfaces: computing shortest non-contractible loops and contractibility testing via Dehn's lemma and a discrete Gauss-Bonnet formula (Lecture 8)
  • Drawing graphs on surfaces: Tutte drawings and Schnyder drawings on the torus (Lecture 7).

LCA's lectures (2025-26): Lecture 1 (slides), TD1 (exercise sheet), Lecture 3 (slides), TD3 (exercise sheet), Lecture 5 (slides), TD5 (exercise sheet), Lecture 7 (slides), TD7 (exercise sheet)

AdM's lectures: Lecture notes, TD2 and correction, TD4 and correction, TD6 and correction, TD8 and correction.

ECdV's lecture notes from previous years: Full lecture notes

• 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

The course has some connections with the following ones:

• [COMBIAA] Algorithmic aspects of combinatorics (website);
• [CGT] Computational Geometry and Topology (website);
• [PARAMALG] Parametrized Algorithms (website);
• [PROBAS] Probability and Algorithmic Applications (website);