Uli Wagner

About me

After that, I spent one semester at the Mathematical Sciences Research Institute in Berkeley, one semester at the Department of Applied Mathematics and the Institute of Theoretical Computer Science at Charles University, Prague, and a year and a half at the Einstein Institute of Mathematics at the Hebrew University of Jerusalem.

Research

My research areas are discrete and computational geometry, i.e., I study geometric problems of a combinatorial or computational nature. A good deal of my research has been motivated by the k-set or halving hyperplane problem and its connections to crossing numbers of graphs, polytope theory, and the combinatorics of linear programming. Here is a survey artice on the topic.

More recently, I have become interested in the interplay between topology, combinatorics, and computation, specifically, in embeddability problems and topological obstructions. Typical questions include: What is the computational complexity of deciding whether a given simplicial complex embeds into Euclidean space of a given dimension? And what consequences does embeddability have for the combinatorics of the complex? The simplest instance of this problem, embedding graphs in the plane, is classical and well-understood, but the situation in higher dimensions is far from being understood.

I have also worked on questions concerning geometric transversals (weak epsilon-nets), manifold learning and reconstruction from points samples, intersection graphs. For more details, you are invited to explore my list of publications below.

My research is supported by the Swiss National Science Foundation (SNF Projects 200021-116741, 20020-125027, and 200021-125309).

Teaching

Courses and seminars I have taught at ETH Zurich since Spring 2006, in reverse chronological order. The links refer to the course webpages, which contain more information

Spring 2009

• Mittagsseminar (with Bernd Gärtner, Dan Hefetz, Michael Hoffmann, Angelika Steger, and Emo Welzl)

• Reading Seminar (with Emo Welzl)

Fall 2008

• Algebraic Methods in Combinatorics (with Dan Hefetz)

• Graphs & Algorithms: Advanced Topics (with Dan Hefetz)

• Mittagsseminar (with Bernd Gärtner, Dan Hefetz, Michael Hoffmann, Angelika Steger, and Emo Welzl)

• Reading Seminar (with Emo Welzl)

Spring 2008

• Topological Methods in Combinatorics and Geometry (with Jiří Matoušek)

• Approximate Methods in Geometry (with Bernd Gärtner and Emo Welzl)

• Mittagsseminar (with Bernd Gärtner, Michael Hoffmann, Angelika Steger, Tibor Szabó, and Emo Welzl)

• Reading Seminar (with Tibor Szabó and Emo Welzl)

Fall 2007

• Mittagsseminar (with Bernd Gärtner, Michael Hoffmann, Angelika Steger, Tibor Szabó, and Emo Welzl)

• Reading Seminar (with Tibor Szabó and Emo Welzl)

Spring 2007

• Discrete Geometry (with Jiří Matoušek)

• Approximate Methods in Geometry (with Bernd Gärtner and Emo Welzl)

• Mittagsseminar (with Bernd Gärtner, Michael Hoffmann, Angelika Steger, Tibor Szabó, and Emo Welzl)

Fall 2006

• Fourier-Analytic Methods in Discrete Mathematics (with Tibor Szabó)

• Mittagsseminar (with Bernd Gärtner, Michael Hoffmann, Angelika Steger, Tibor Szabó, and Emo Welzl)

Spring 2006

• Approximate Methods in Geometry (with Bernd Gärtner and Emo Welzl)

• Mittagsseminar (with Bernd Gärtner, Stefanie Gerke, Michael Hoffmann, Angelika Steger, Tibor Szabó, and Emo Welzl)

Publications

• Uli Wagner and Emo Welzl
  A Continuous Analogue of the Upper Bound Theorem (ps.gz, pdf)
  Discrete & Computational Geometry 26 (2) (2001), pp. 205-219.

  An extended abstract appeared in Proc. 16th Annual ACM Symposium on Computational Geometry (SoCG), 2000, pp. 50-56.

• Uli Wagner
  On the Number of Corner Cuts (ps.gz, pdf)
  Advances in Applied Mathematics, 29 (2002), pp. 152-161.

• Christoph Ambühl and Uli Wagner
  The Clique Problem in Intersection Graphs of Ellipses and Triangles (ps.gz, pdf)
  Theory of Computing Systems 38 (2), 2005, 279-292.

  An extended abstract appeared Proc. 13th Annual International Symposium on Algorithms and Computation (ISAAC), 2002, pp. 489-500.

• Uli Wagner
  On the Rectilinear Crossing Number of Complete Graphs (ps.gz, pdf)
  Proc. 14th Annual Symposium on Discrete Algorithms (SODA), 2003, pp. 583-588.

• Jiri Matousek and Uli Wagner
  New Constructions of Weak Epsilon-Net (ps.gz, pdf)
  Discrete & Computational Geometry 32 (2) (2004), pp. 195-206.

  An extended abstract appeared in Proc. 19th Annual ACM Symposium on Computational Geometry (SoCG), 2003, pp. 129-135.

• Joachim Giesen and Uli Wagner
  Shape Dimension and Intrinsic Metric From Samples of Manifolds with High Co-Dimension (ps.gz, pdf)
  Discrete & Computational Geometry 32 (2) (2004), pp. 245-267.

  An extended abstract appeared in Proc. 19th Annual ACM Symposium on Computational Geometry (SoCG), 2003, pp. 329-337.

• László Lovász, Katalin Vesztergombi, Uli Wagner, and Emo Welzl
  Convex Quadrilaterals and k-Sets (ps.gz, pdf)
  Towards a Theory of Geometric Graphs (János Pach, ed.), Contemporary Mathematics 342, American Mathematical Society, Providence, 2004, pp. 139-148.

• Jiri Matousek, Micha Sharir, Shakhar Smorodinsky, and Uli Wagner
  k-Sets in 4 dimensions (pdf)
  Discrete & Computational Geometry 35(2) (2006), pp. 177-191.

• Jorgen Bang-Jensen, Bruce Reed, Mathias Schacht, Robert Sámal, Bjarne Toft, and Uli Wagner
  On six problems posed by Jarik Nesetril (ps.gz, pdf)
  Topics in Discrete Mathematics (Martin Klazar, Jan Kratochvil, Martin Loebl, Jiri Matousek, Robin Thomas, eds.),
  Algorithms and Combinatorics 26 (2006), pp. 613--627.

• Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Jiri Matousek, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, and Emo Welzl
  Online conflict-free coloring for intervals (pdf)
  Siam Journal of Computing 36(5) (2006), pp. 1342--1359.

  An extended abstract appeared in Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005.

• Uli Wagner.
  On a Geometric Generalization of the Upper Bound Theorem (pdf)
  Proc. 47th Annual Symposium on the Foundations of Computer Science (FOCS), 2006, pp. 635-645.

• Uli Wagner.
  k-Sets and k-Facets (pdf)
  Discrete and Computational Geometry - 20 Years Later (Eli Goodman, János Pach, and Ricky Pollack, eds.), Contemporary Mathematics 453, American Mathematical Society, to appear.

• Kevin Buchin, Andreas Razen, Takeaki Uno, and Uli Wagner.
  Transforming Spanning Trees (pdf)
  Computational Geometry: Theory and Appications, to appear.

• Eran Nevo and Uli Wagner.
  On the Embeddability of Skeleta Spheres (pdf)
  Israel Journal of Mathematics, to appear.

• Jiri Matousek, Martin Tancer, and Uli Wagner.
  Hardness of Embedding Simplicial Complexes in R^d (pdf)
  Journal of the European Mathematical Society, to appear.