Discrete and Computational Geometry and Topology
Mathematics
1 Career
- Since 2018 Professor, Institute of Science and Technology Austria (ISTA)
- 2013 – 2018 Assistant Professor, Institute of Science and Technology Austria (ISTA)
- 2012 – 2013 SNSF Research Assistant Professor, Institut de Mathématiques de Géométrie et Applications, EPFL, Lausanne, Switzerland
- 2008 – 2012 Senior Research Associate, Institute of Theoretical Computer Science, ETH Zürich, Switzerland
- 2006 – 2008 Postdoc, Institute of Theoretical Computer Science, ETH Zürich, Switzerland
- 2004 – 2006 Postdoc, Einstein Institute for Mathematics, The Hebrew University of Jerusalem, Israel
- 2004 Postdoc, Department of Applied Mathematics, Univerzita Karlova, Prague; Czech Republic
- 2004 Ph.D., ETH Zürich, Switzerland
- 2003 Member, Mathematical Sciences Research Institute, Berkeley, USA
1.1 Selected Distinctions
- 2018 Best Paper Award at the Symposium on Computational Geometry (SoCG) for the paper Shellability is NP-complete (joint with Goaoc, Paták, Patáková, and Tancer)
- 2014 Best Paper Award at the Symposium on Computational Geometry (SoCG) for the paper
Embeddability in the 3-sphere is decidable (joint with Sedgewick, Matoušek, and Tancer) - 2012 Best Paper Award at the Symposium of Discrete Algorithms (SODA) 2012 for the pa-
per Computing all maps into a sphere (joint with Čadek, Krčál, Matoušek, Sergeraert, and Vokřínek) - 2004 Richard Rado Prize
1.2 Selected Grants
- 2018 – 2022 Austrian Science Fund (FWF) project P 31312-N35 Algorithms for Embeddings and Homotopy Theory
1.3 Tech Transfer (Patents, Spin-Offs)
N/A
1.4 Selected Publications
- S. Avvakumov, M. Filakovský, J. Opršal, G. Tasinato, and U. Wagner, “Hardness of 4-colouring G-colourable graphs,” in STOC’25—Proceedings of the 57th Annual ACM Symposium on Theory of Computing, ACM, New York, 2025, pp. 72–83. DOI: https://doi.org/10.1145/3717823.3718154.
- E. Streltsova and U. Wagner, “Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers,” in 41st International Symposium on Computational Geometry, ser. LIPIcs. Leibniz Int. Proc. Inform. Vol. 332, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2025, Art. No. 75, 18. [Online]. Available: https://doi.org/10.4230/lipics.socg.2025.75.
- U. Wagner and P. Wild, “Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes,” Israel J. Math., vol. 256, no. 2, pp. 675–717, 2023. DOI: https://doi.org/10.1007/s11856-023-2521-9.
- U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the plane,” Discrete Comput. Geom., vol. 68, no. 4, pp. 1227–1284, 2022. DOI: https://doi.org/10.1007/s00454-022-00436-2.
- X. Goaoc, P. Paták, Z. Patáková, M. Tancer, and U. Wagner, “Shellability is NP-complete,” J. ACM, vol. 66, no. 3, 21:1–21:18, 2019. DOI: https://doi.org/10.1145/3314024.
2 Group Members
- Daniel Bedats, PhD Student since 2024
- Irene Pisapia, PhD Student since 2025 (co-supervised with Herbert Edelsbrunner)
- Elizaveta Streltsova, PhD Student since 2021
- Valentina Disarlo, Postdoc since 2024
- Raphaël Tinarrage, Postdoc since 2024
3 Research
The group works on problems at the interface between geometry and topology, discrete mathematics, and theoretical computer science, more specifically in topological and geometric combinatorics and computational geometry and topology. On the one hand, we study classical topological questions (such as embeddability, or the classification of continuous maps up to homotopy) from a computational and quantitative viewpoint. On the other hand, we apply topological methods and ideas to questions in discrete mathematics and theoretical computer science (such as graph coloring and other constraint satisfaction problems, levels in arrangements, triangulations of planar point sets, or Tverberg-type problems), which, in turn, may lead to interesting topological questions and new techniques (e.g., discrete isoperimetric inequalities, higher-multiplicity Whitney tricks, etc.).
With a view towards algorithms and combinatorial applications, we mostly work in a discrete setting where spaces are represented as simplicial complexes. Viewing simplicial complexes as a natural higher-dimensional generalizations of graphs, a good part of our research can be seen, from a combinatorial perspective, as studying higher-dimensional analogues of fundamental graph-theoretic notions such as graph planarity, crossing numbers, and expansion.
3.1 Current Scientific Projects/Directions
- Topology and the computational complexity of constraint satisfaction problems
- High-dimensional expansion and crossing numbers
- Polytopes and levels in arrangements
- Triangulations of planar point sets
3.2 Research in Focus
Graph coloring plays a central role in combinatorics and in theoretical computer science. In particular, it is a classical result in computational complexity theory, proved by Karp in 1972, that it is computationally intractable () to decide whether a given finite graph is 3-colorable (or, more generally, -colorable, for a fixed ≥ 3). Since then, the complexity of approximating the chromatic number of a graph has been studied extensively, but the following approximate graph coloring problem remains wide open: Given an input graph that is guaranteed to be 3-colorable (but we are not given a 3-coloring), what is the computational complexity of finding a proper coloring of with some larger number > 3 of colors? It is conjectured that this problem is for every fixed , but currently this is known only for ∈ {4, 5}.
More generally, a graph homomorphism between two finite graphs is a map between their vertex sets that preserves edges; for example, a proper -coloring of is the same as a homomorphism , where is the complete graph on vertices. Let be a fixed graph. By a famous result of Hell and Nešetřil from 1990, the problem of deciding whether a given input graph admits a homomorphism is either trivially solvable in polynomial time (if is bipartite or has a loop) or otherwise. As a common generalization of this and approximate graph coloring, consider two finite graphs and such that there exists a homomorphism . Given a finite input graph that admits an (unknown) homomorphism to , what is the computational complexity of finding a homomorphism to ? If is bipartite or has a loop, this is trivially solvable in polynomial time; Brakensiek and Guruswami conjectured that in all other cases, this problem is .
In joint work with two former students, Sergey Avvakumov and Gianluca Tasinato, and two former postdocs, Marek Filakovský and Jakub Opršal, we used topological methods to prove the Brakensiek–Guruswami Conjecture in the case when is 4-colorable; this result appeared in the Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC’25) [1].