Table of Contents
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?2023-08-30: Warning: The first lecture will take place in the “Halle aux Farines” building, room 381F. The other lectures will take place in room 1002 of the Sophie Germain building. 2023-08-23: Web page updated for 2023-2024 academic year. The tentative contents of the lectures and the preliminary roadmap still have to be updated. Practical informationWhen? First period, Thursdays, from 8:45 to 11:45, starting September 14. The tentative contents of the lectures is as follows:
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 themeAlgorithms 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
Preliminary roadmap
Course notes and slidesLCA's lectures: Lecture 1 ÉCdV's lectures: course notes (only a subset will be treated) Bibliography
Relevant coursesThe course has some connections with the following ones: |