# 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=**R**^{d}. Given a space X, can we decide whether X can be embedded (without self-intersections) into **R**^{d}?

3. Assuming that a space X embeds into **R**^{d}, 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 **R**^{2}) 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.

**Contact**

Uli Wagner

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

**Assistant**

Elisabeth Hacker

Phone: +43 (0)2243 9000-1015

E-mail: elisabeth.hacker@
ist.ac.at

**Team**

- Marek Krcal, Postdoc
- Isaac Mabillard, PhD Student
- Martin Tancer, Postdoc

**Selected Publications**

- Matoušek M, 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 M, Tancer M, Wagner U. Hardness of embedding simplicial complexes in Rd, J. Eur. Math. Soc. 13(2), 2011, 259–295.

**Career**

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

**Selected Distinctions**

2014 Co-winner of Best Paper Award at the Symposium on Computational Geometry (SoCG)

2012 Research Assistant Professorship Grant of Swiss National Science Foundation (SNSF)

2012 Co-winner of Best Paper Award at Symposium of Discrete Algorithms (SODA)

2004 Richard Rado Prize