 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 kset 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 wellunderstood, but in higher dimensions,
many fundamental questions are still unresolved.
I have also worked on questions concerning geometric transversals
(weak epsilonnets), 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 200021116741, 20020125027, 200021125309, and 200020138230).


Publications

Uli Wagner and Emo Welzl
A Continuous Analogue of the Upper Bound Theorem
(ps.gz,
pdf)
Discrete & Computational Geometry 26 (2) (2001), pp. 205219.
An extended abstract appeared in Proc. 16th Annual ACM
Symposium on Computational Geometry (SoCG), 2000, pp. 5056.

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

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, 279292.
An extended abstract
appeared in Proc. 13th Annual International
Symposium on Algorithms and Computation (ISAAC), 2002,
pp. 489500.

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

Jiří Matoušek
and Uli Wagner
New Constructions of Weak EpsilonNet
(ps.gz,
pdf)
Discrete & Computational Geometry 32 (2) (2004), pp. 195206.
An extended abstract appeared in Proc. 19th Annual ACM
Symposium on Computational Geometry (SoCG), 2003, pp. 129135.

Joachim Giesen and Uli
Wagner
Shape Dimension and Intrinsic Metric From Samples of Manifolds with High
CoDimension (ps.gz, pdf)
Discrete & Computational Geometry 32 (2) (2004), pp. 245267.
An extended abstract appeared in Proc. 19th Annual ACM
Symposium on Computational Geometry (SoCG), 2003, pp. 329337.

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

Jiří Matoušek,
Micha Sharir, Shakhar Smorodinsky, and Uli Wagner
kSets in 4 dimensions
(pdf)
Discrete & Computational Geometry
35(2) (2006), pp. 177191.

Jørgen BangJensen, Bruce Reed, Mathias Schacht, Robert Šá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. 613627.

Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Jiří Matoušek, Elchanan Mossel, János
Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, and Emo Welzl
Online conflictfree coloring for intervals
(pdf)
Siam Journal of Computing 36(5)
(2006), pp. 13421359.
An extended abstract appeared in
Proc. 16th Annual ACMSIAM 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. 635645.

Uli Wagner.
kSets and kFacets
(pdf)
Discrete and Computational Geometry  20 Years Later
(Eli Goodman, János Pach, and Ricky Pollack, eds.), Contemporary Mathematics 453,
American Mathematical Society, 2008, 443514.

Shakhar Smorodinsky, Marek Sulovský,
and Uli Wagner
On Center Regions and Balls Containing Many Points
Proc. 14th Annual International Conference on Computing and Combinatorics (COCOON), 2008, pp. 363373.

Kevin Buchin, Andreas Razen, Takeaki Uno, and Uli Wagner.
Transforming Spanning Trees
(pdf)
Computational Geometry: Theory and Appications 42(8) (2009), pp. 724730.

Eran Nevo and Uli Wagner.
On the Embeddability of Skeleta of Spheres
(pdf)
Israel Journal of Mathematics 174 (2009), pp. 381402.

Jiří Matoušek,
Martin Tancer, and
Uli Wagner.
Hardness of Embedding Simplicial Complexes in R^{d}
(pdf)
Journal of the European Mathematical Society 13 (2011), pp. 259295.
An extended abstract appeared in
Proc. 20th Annual ACMSIAM Symposium on
Discrete Algorithms (SODA), 2009.

Jiří Matoušek,
Martin Tancer,
and Uli Wagner
A Geometric Proof of the Colored Tverberg Theorem
(pdf)
Discrete & Computational Geometry
47(2) (2012), pp. 245265.
(DOI: 10.1007/s0045401193682)

Uli Wagner
Minors in Random and Expanding Hypergraphs
(pdf)
Proc. 27th Annual ACM
Symposium on Computational Geometry (SoCG), 2011, pp. 351360.

Martin Čadek, Marek Krčál, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek, and Uli Wagner
Computing all maps into a sphere
(arXiv preprint)
Proceedings of the 23rd Annual Symposium on Discrete Algorithms (SODA), 2012, pp. 110.

Anna Gundert and Uli Wagner
On Laplacians of Random Complexes
(pdf)
Proc. 28th Annual ACM
Symposium on Computational Geometry (SoCG), 2012, to appear.
Coauthors
Christoph Ambühl,
Jørgen BangJensen,
Kevin Buchin,
Ke Chen,
Martin Čadek,
Amos Fiat,
Joachim Giesen,
Anna Gundert,
Haim Kaplan,
Marek Krčál,
Meital Levy,
László Lovász,
Jiří Matoušek,
Elchanan Mossel,
Eran Nevo,
János Pach,
Andreas Razen,
Bruce Reed,
Mathias Schacht,
Francis Sergeraert,
Micha Sharir,
Shakhar Smorodinsky,
Marek Sulovský,
Robert Šámal,
Martin Tancer,
Bjarne Toft,
Takeaki Uno,
Katalin Vesztergombi,
Lukáš Vokřínek,
Emo Welzl

 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
Fall 2011
Spring 2011
Mittagsseminar
(with Bernd Gärtner, Dan Hefetz, Michael Hoffmann, Johannes Lengler, Gabriel Nivasch,
Angelika Steger, and Emo Welzl)
Reading Seminar (with Emo
Welzl)
Fall 2010
Spring 2010
Metric Embeddings
(with Jiří Matoušek)
Mittagsseminar
(with Bernd Gärtner, Dan Hefetz, Michael Hoffmann, Gabriel Nivasch,
and Emo Welzl)
Reading Seminar (with Emo
Welzl)
Fall 2009
Spring 2009
Fall 2008
Spring 2008
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
Fall 2006
Spring 2006
