Table of Contents
## 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
## 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 - 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 roadmapThe 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 notesA 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 coursesThe course has some connections with the following ones: Additionally, this course fits well within a coherent list of courses on the theme “Algorithms and Complexity”, whose other courses are: |