Discrete and Computational Geometry and Topology
The research of the group focuses on questions in combinatorial and computational geometry and topology. On the one hand, we study basic questions in geometry and topology from a combinatorial and algorithmic viewpoint. On the other hand, we apply methods from topology to problems in combinatorics, discrete geometry, and theoretical computer science.
For the purpose of algorithms and applications, we typically consider the geometric shapes (topological spaces) we study to be represented as simplicial complexes, i.e., in terms of a combinatorial description of how to build the space from basic building blocks (simplices) of various dimensions — points (vertices), line segments (edges), triangles, tetrahedra, etc. For example, a one-dimensional simplicial complex is just a graph, given by a set of vertices and a description which pairs of vertices are joined by an edge (e.g., the layout of a computer chip or a network); higher-dimensional complexes also encode interactions between three and more vertices.
Here are some typical questions we study:
1. Given spaces X and Y, can we compute [X,Y], the set of all continuous functions from X to Y up to homotopy (continuous deformation of one function into another)?
This is a classical topic in algebraic topology. Our focus is on the question to what extent this can be done in a mechanical, automated way, i.e., by a computer program.
2. Fix a simple target space, e.g. Y=Rd. Given a space X, can we decide whether X can be embedded (without self-intersections) into Rd?
3. Assuming that a space X embeds into Rd, what can we say about its structure and its combinatorial complexity (number of simplices)?
Embeddings are also a classical topic in geometric topology. On the other hand the most basic special case of these questions, graph planarity (embedding a one-dimensional space, a graph, into the plane R2) is also a fundamental topic in graph theory and theoretical computer science that has led to a rich combinatorial and algorithmic theory with many applications. Thus, one of our goals is to study higher-dimensional generalizations of graph planarity and of closely related concepts such as graph minors, crossing numbers, expander graphs, etc.
Institute of Science and Technology Austria (IST Austria)
Am Campus 1
A – 3400 Klosterneuburg
Phone: +43 2243 9000 5501
E-mail: uli.wagner@ ist.ac.at
Astrid Bonventre-Darthe (Assistant to Professor)
Phone: +43 (0)2243 9000-1015
E-mail: astrid.bonventre-darthe@ ist.ac.at
- Marek Filakovský, Postdoc
- Peter Franek, Postdoc (supported by FWF)
- Radoslav Fulek, Postdoc (ISTFellow)
- Kristóf Huszár, PhD Student
- Marek Krčál, Postdoc
- Isaac Mabillard, PhD Student (supported by SNSF)
- Zuzana Masárová , PhD Student (jointly affiliated with Edelsbrunner Group)
- Stephan Zhechev, PhD Student
- Mabillard, I, Wagner U. Eliminating Tverberg points, I. An analogue of the Whitney trick. Proc. 30th Ann. ACM Symp. on Comput. Geom. (SoCG), 2014, 171–180.
- Matoušek J, Sedgwick, E, Tancer M, Wagner U. Embeddability in the 3-sphere is decidable. Proc. 30th Ann. ACM Symp. on Comput. Geom. (SoCG), 2014, 78–84.
- Čadek M, Krčál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. Computing all maps into a sphere. Proc. 23rd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), 2012, 1–10.
- Wagner U. Minors in Random and Expanding Hypergraphs. Proc. 27th Ann. ACM Symp. on Comput. Geom. (SoCG), 2011, 351–360.
- Matoušek J, Tancer M, Wagner U. Hardness of embedding simplicial complexes in Rd, J. Eur. Math. Soc. 13(2), 2011, 259–295.
Since 2013 Assistant Professor, IST Austria
2012-2013 SNSF Research Assistant Professor, Institut de Mathématiques de Géométrie et Applications, EPFL Lausanne
2008–2012 Senior Research Associate, Institute of Theoretical Computer Science, ETH Zurich
2006–2008 Postdoctoral Researcher, Institute of Theoretical Computer Science, ETH Zürich
2004–2006 Postdoctoral Fellow, Einstein Institute for Mathematics, The Hebrew University of Jerusalem
2004–2004 Postdoctoral Fellow, Department for Applied Mathematics, Univerzita Karlova, Prague
2003–2003 Postdoctoral Fellow, Mathematical Sciences Research Institute, Berkeley
2000–2004 PhD in Mathematics, ETH Zurich
1995–2000 Diplom in Mathematics, Freie Universität Berlin
2014 Best Paper Award at the Symposium on Computational Geometry (SoCG)
2012 Research Assistant Professorship Grant of Swiss National Science Foundation (SNSF)
2012 Best Paper Award at Symposium of Discrete Algorithms (SODA)
2004 Richard Rado Prize