Graphs and Surfaces: Algorithms, Combinatorics and Topology
May 9 – 13, 2016

This Spring School in Theoretical Computer Science will be about topological graphs, which can be represented in the plane or more generally on a surface, or in space.  Graphs are a fundamental tool in computer science, and very often arise from geometry.  For example, they can be drawn in the plane with no or few crossings, or on a topologically simple surface.  Such graphs bear structural properties that allow to solve algorithmic problems more efficiently than on general abstract graphs.  Moreover, specific questions, of a combinatorial or topological nature, are relevant for these graphs.

This research school aims at presenting an introduction to the various aspects of topological graphs: computational, combinatorial, structural, topological, etc., and at their interactions.  This theme is thus located at the crossroad of various fields of mathematics and theoretical computer science: enumerative and bijective combinatorics, low-dimensional topology, algorithms and structural graph theory, computational geometry. It is targeted to interested students and researchers in mathematics and theoretical computer science, and especially to PhD students and young researchers.  There is no prerequisite, as all useful notions will be introduced.

Lectures will be given in French or English.  Course notes and slides will be in English.

Scientific Committee

Éric Colin de Verdière (ENS Paris)
Frédéric Magniez (Université Paris Diderot)
Gilles Schaeffer (Ecole polytechnique)

Organizing Committee

Éric Colin de Verdière (ENS Paris)
Gilles Schaeffer (Ecole polytechnique)



Topological aspects

  • Bojan Mohar (Simon Fraser University & University of Ljubljana) 

Structural aspects

Combinatorial aspects

Computational aspects

Short Courses:

Coloring aspects

Higher-dimensional aspects