The graph planarity testing problem asks whether we can draw an input graph in the plane in such a way that it is actually crossing-free (or embedded). In a seminal paper from 1974, Hopcroft and Tarjan gave a linear-time algorithm for this problem, initiating a long series of variations and generalizations. One of them is to make the target space more general, namely, to consider embeddings not into the plane, but into a more general surface. It is known that the problem of deciding the embeddability of a graph into a surface is NP-hard, but Mohar (1999) and Kawarabayashi, Mohar, and Reed (2008) gave algorithms that are linear in the size of the graph (and exponential in the genus of the surface).
In this talk, we consider an even more general case, in which the target space is a 2-dimensional simplicial complex (a topological space obtained from a graph by attaching a solid triangle to some of its 3-cycles). It turns out that this generalization encompasses some other well known problems, such as the crossing number, the splitting number, and the planarity number (and their generalizations to surfaces). We give an algorithm that is quadratic in the size of the input graph (and exponential in the size of the input complex), independent from the previous algorithms to embed graphs into surfaces. The techniques mix graph theory (branchwidth, excluded grid theorem, dynamic programming) with topology (combinatorial maps of graphs on surfaces).
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne