FoCM 2014 conference

Workshop B2 - Computational Topology and Geometry

December 17, 17:00 ~ 17:25 - Room A22

Embeddings of Simplicial Complexes $- $ Algorithms $\&$ Combinatorics

Uli Wagner

IST Austria, Austria   -

We survey a number of results and open questions concerning (from a combinatorialist's point of view) higher-dimensional analogues of graph planarity and crossing numbers, i.e., embeddings of finite simplicial complexes (compact polyhedra) into Euclidean space and other ambient manifolds.

While embeddings are a classical topic in geometric topology, here we focus rather on algorithmic and combinatorial aspects. Two typical questions are the following:

(1) Is there an algorithm that, given as input a finite k-dimensional simplical complex, decides whether it embeds in d-dimensional space?

(2) What is the maximum number of k-dimensional simplices of a simplicial complex that embeds into d-dimensional space?

Time permitting, we will also discuss some maps with more general restrictions on the set of singularities, e.g., maps without r-fold intersection points.

Joint work with Martin Cadek (Masaryk University, Brno), Xavier Goaoc (Universite Paris-Est), Marek Krcal (IST Austria), Isaac Mabillard (IST Austria), Jiri Matousek (Charles University, Prague), Pavel Patak (Charles University, Prague), Zusana Safernova (Charles University, Prague), Francis Sergeraert (Institut Fourier, Grenoble), Eric Sedgwick (DePaul University, Chicago), Martin Tancer (IST Austria) and Lukas Vokrinek (Masaryk University, Brno).

View abstract PDF