Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
Institut für Theoretische Informatik | ||
Departement Informatik | ||
ETH Zürich | phone | +41-44-632 73 92 |
CH-8092 Zürich | fax | +41-44-632 10 63 |
Quick Links: | Personnel, Guests, Grants, Publications, Lectures, Courses, Workshops, Dissertations, Master Theses, Bachelor Theses, Miscellaneous, Software |
(Financed by the Swiss National Science Foundation - EuroGIGA/ComPoSe). The goal of this project is the understanding of crossing-free geometric graphs-these are graphs with an embedding on a given planar point set where the edges are drawn as straight line segments without crossings. Often we are restricted to certain types of graphs, most prominently triangulations, but also spanning cycles, spanning trees or (perfect) matchings (and crossing-free partitions), among others. A primary goal is to enumerate, count, or sample graphs of a certain type for a given point set-so these are algorithmic questions-, or to give estimates for the maximum and minimum number of such graphs on any set of n points-these are problems in extremal combinatorial geometry.
Contact: E. Welzl, M. Wettstein
(Financed by the Department of Computer Science, ETH Zürich, Haslerstiftung , Akademie der Wissenschaften der Schweiz). Zusammen mit dem Departement für Informatik der ETH Zurich errichtet das Kinderlabor ein hochqualitatives und gleichzeitig allgemein zugänglichen Weiterbildungsangebot in Informatik. Zielgruppe sind Lehrpersonen in Kindergarten und Unterstufe der Primarschule (1. / 2. Klasse), auch ohne Informatik-Vorkenntnisse. In den Kursen lernen die Teilnehmenden die sogenannten Bee-Bots kennen. Das sind kindlich gestaltete Bodenroboter in Bienenform. Sie können mit vier Richtungstasten so programmiert werden, dass sie vorgegebene Wege laufen können. Zusammen mit den Bee-Bots werden passende Unterrichtsmaterialien vorgestellt und eingesetzt. Nach dem Kurs können Lehrpersonen eine „Bee-Bot-Kiste“ für die Dauer von 2 – 4 Wochen ausleihen. Auf Wunsch kommt ein Studierender der Informatik der ETH Zürich in die Klasse, um die Lehrperson beim Einsatz zu unterstützen und zu coachen.
Contact: B. Gärtner.
(Financed by the Swiss National Science Foundation). Understanding and removing redundancy in a given data to improve computational efficiency or discover its fundamental structure is a universal problem in science and engineering, as the data or the mathematical model to be analyzed in any realistic situation often contains redundant information that is implied by the rest. This research project has two intertwined goals, one of them theoretical, the other one driven by a concrete application. On the theoretical level, we want to understand the structure of redundancy and the complexity of redundancy removal in explicitly or implicitly given linear and more abstract systems. Here we strongly build on our expertise in computational geometry as well as combinatorial optimization. On the application side, we want to compute redundancy and assess the role of redundancy in neuromuscular control, a field that is trying to understand how the nervous system is selecting and implementing specific muscle commands that meet the constraints of specific tasks. This part of the project will be performed in close collaboration with Francisco Valero-Cuevas. He pioneered in modeling the interplay of various muscles in terms of zonotopes whose internal structure determines the possible tasks that the muscles under consideration can achieve together.
Contact: B. Gärtner, K. Fukuda
(Financed by the Swiss National Science Foundation). We use the term simultaneous (geometric) embedding to refer to any kind of problem in which two or more graphs are to be embedded simultaneously, usually subject to certain constraints. One reason for the strong interest in simultaneous embeddings lies in a wealth of applications in areas such as bio-informatics, network analysis, and software engineering. For instance, in order to compare two phylogenetic trees one would like to have a "nice" simultaneous drawing of two trees sharing the same set of leaves, so-called tanglegrams. More generally, simultaneous embeddings come into play whenever large or dynamically changing graphs are to be visualized. Given a large graph, only part of it can be shown at a time with a sufficient level of detail. When browsing from one such part to a neighboring one, it is desirable to have a certain overlap that is common to both parts and drawn the same way for both parts. In this way, the user can maintain her mental map and more easily keep track of her current location in the graph. In the context of dynamic graphs, a simultaneous drawing for several instances of the graph at different timesteps allows to visually examine the differences in order to, for instance, draw conclusions regarding the capacity utilization of a network. Beyond these motivating applications the study of simultaneous embeddings revealed a rich collection of interesting and challenging combinatorial and algorithmic problems, many of which are still far from being solved. The goal of this project is, on one hand, to gain more insights into some of these problems and, on the other hand, to develop new models in order to address some shortcomings of the existing settings studied so far. The project will be carried out as an international collaboration within the collaborative research project "GraDr: Graph Drawings and Representations", which comprises altogether 12 partners from seven European countries.
Contact: M. Hoffmann, V. Kusters
O. Aichholzer, G. Aloupis, E. Demaine, M. Demaine, M. Hoffmann, S. Fekete, A. Lubiw, J. Snoeyink, A. Winslow, Covering Folded Shapes, Journal of Computational Geometry , 5:1 (2014), 150-168.
O. Aichholzer, J. Cardinal, Th. Hackl, F. Hurtado, M. Korman, A. Pilz, R. I. Silveira, R. Uehara, B. Vogtenhuber, E. Welzl, Cell-Paths in Mono- and Bichromatic Line Arrangements in the Plane, Discrete Mathematics & Theoretical Computer Science, 16:3 (2014), 317-332.
O. Aichholzer, T. Hackl, M. Hoffmann, A. Pilz, G. Rote, B. Speckmann, B. Vogtenhuber, Plane Graphs with Parity Constraints, Graphs and Combinatorics, 30:1 (2014), 47-69.
A. Baertschi, S. Suri, Conflict-free chromatic art gallery coverage, Algorithmica 68:1 (2014), 265-283.
B. Bukh, J. Matoušek, Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1, Duke Mathematical Journal 163:12 (2014), 2243-2270.
M. Čadek, M. Krčál, J. Matoušek, L. Vokřínek, U. Wagner, Extendability of continuous maps is undecidable, Discrete & Computational Geometry 51:1 (2014), 24-66.
M. Čadek, M. Krčál, J. Matoušek, L. Vokřínek, U. Wagner, Polynomial-time computation of homotopy groups and Postnikov systems in fixed dimension, SIAM J. Computing 43:5 (2014), 1728-1780.
M. Čadek, M. Krčál, J. Matoušek, F. Sergeraert, L. Vokřínek, U. Wagner, Computing all maps into a sphere, Journal of the ACM 61:3 (2014), Article No.: 17.
M. Elias, J. Matoušek, E. Roldán-Pensado, Z. Safernová, Lower bounds on geometric Ramsey functions, SIAM J. Discrete Math. 28:4 (2014), 1960-1970.
J. Foniok, B. Gärtner, L. Klaus, M. Sprecher, Counting Unique-Sink Orientations, Discrete Applied Mathematics 163:2 (2014), 155-164.
F. Frati, J. Gudmundsson, E. Welzl, On the Number of Upward Planar Orientations of Maximal Planar Graphs, Theoretical Computer Science 544 (2014), 32-59.
T. Hertli, 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General, SIAM Journal of Computing 43:2 (2014), 718-729.
M. Hoffmann and Cs.D. Tóth, Vertex-Colored Encompassing Graphs, Graphs and Combinatorics 30:4 (2014), 933-947.
J. Matoušek, Near-optimal separators in string graphs, Combinatorics, Probability and Computing 23:1 (2014), 135-139.
J. Matoušek, U. Wagner, On Gromov's method of selecting heavily covered points, Discrete and Computational Geometry 52:1 (2014), 1-33.
H. Tyagi, V. Cevher, Learning non-parametric basis independent models from point queries via low-rank methods, Applied and Computational Harmonic Analysis 37:3 (2014), 389-412.
O. Aichholzer, J. Cardinal, V. Kusters, S. Langerman, P. Valtr, Reconstructing Point Set Order Types from Radial Orderings, Proc. 25th International Symposium on Algorithms and Computation (ISAAC) (2014) LNCS 8889, 15-26.
I. Bárány, J. Matoušek, A. Por, Curves in Rd intersecting every hyperplane at most d+1 times, Proc. 30th Annual ACM Symposium on Computational Geometry (SoCG) (2014), 565-574.
K. Buchin, A. van Goethem, M. Hoffmann, M. van Kreveld, B. Speckmann. Travel-time Maps: Linear Cartograms with Fixed Vertex Locations, Proc. 8th International Conference on Geographic Information Science (GIScience) (2014) LNCS 8728, 18-33.
M. Elias, J. Matoušek, E. Roldán-Pensado, Z. Safernová, Lower bounds on geometric Ramsey functions, Proc. 30th Annual ACM Symposium on Computational Geometry (SoCG) (2014), 558-564.
W. Evans, V.Kusters, M. Saumell, B. Speckmann, Column Planarity and Partial Simultaneous Geometric Embedding, 22nd International Symposium on Graph Drawing (2014) LNCS 8871, 259-271.
A. Francke, Cs.D. Tóth, A Census of Plane Graphs with Polyline Edges, Proc. 30th Annual ACM Symposium on Computational Geometry (SoCG) (2014), 242-250.
B. Gärtner, Sampling with Removal in LP-type Problems, Proc. 30th Annual ACM Symposium on Computational Geometry (SoCG) (2014), 511-518.
B. Gärtner, A. Krause, H. Tyagi, Efficient Sampling for Learning Sparse Additive Models in High Dimensions, Advances in Neural Information Processing Systems (NIPS) (2014), 514-522.
B. Gärtner, H. Tyagi, Continuum armed bandit problem of few variables in high dimensions, Proc. 11th Workshop on Approximation and Online Algorithms (WAOA) (2014) LNCS 8447, 108-119.
A. Gundert, M. Szedlák, Higher Dimensional Discrete Cheeger Inequalities, Proc. 30th Annual ACM Symposium on Computational Geometry (SoCG) (2014), 181-188.
T.Hertli, Breaking the PPSZ Barrier for Unique 3-SAT, 41st International Colloquium on Automata, Languages and Programming (ICALP) (2014) LNCS 8572, 600-611.
M. Hoffmann, V. Kusters, T. Miltzow, Halving Balls in Deterministic Linear Time, Proc. 22nd Annual European Symposium on Algorithms (ESA) (2014) LNCS 8737, 566-578.
J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Embeddability in the 3-sphere is decidable, Proc. 30th Annual ACM Symposium on Computational Geometry (SoCG) (2014), 78-87.
S. Stich, On low complexity Acceleration Techniques for Randomized Optimization, 13th International Conference on Parallel Problem Solving From Nature (PPSN) (2014) LNCS 8672, 130-140.
M. Wettstein, Counting and Enumerating Crossing-free Geometric Graphs, Proc. 30th Annual ACM Symposium on Computational Geometry (SoCG) (2014), 1-10.
O. Aichholzer, Th. Hackl, M. Korman, M. van Kreveld, M. Löffler, A. Pilz, B. Speckmann, E. Welzl, Packing Plane Spanning Trees and Paths in Complete Geometric Graphs, Proc. 26th Canadian Conference on Computational Geometry (CCCG) (2014), 6 pages.
O. Aichholzer, M. Hoffmann, M. van Kreveld, G. Rote, Graph Drawings with Relative Edge Length Specifications Proc. 26th Canadian Conference on Computational Geometry (CCCG) (2014), 7 pages.
Y. Brise, K. Buchin, D. Eversmann, M. Hoffmann, W. Mulzer, Interference Minimization in Asymmetric Sensor Networks, Proc. 10th International Symposium on Algorithms and Experiments for Sensor Systems (ALGOSENSORS) (2014), 16 pages.
M. Hoffmann, M. van Kreveld, V. Kusters, G. Rote, Quality Ratios of Measures for Graph Drawing Styles, Proc. 26th Canadian Conference on Computational Geometry (CCCG) (2014), 7 pages.
M. Hoffmann, V. Kusters, T. Miltzow, Separating Balls with a Hyperplane, Abstracts of the 30th European Workshop on Computational Geometry (EuroCG), Ein-Gedi, Israel (2014).
J. Matoušek, String graphs and separators (expository paper), in J. Matoušek, J. Nesetril, M. Pellegrini (eds.): Geometry, Structure and Randomness in Combinatorics, CRM Series, Springer, (2014).
T. HERTLI
"Breaking the PPSZ Barrier for Unique 3-SAT", CSE Theory Seminar, UC San Diego, USA (Jan 27, 2014).
M. HOFFMANN
"Graph Drawings with Relative Edge Length Specifications", 26th Canadian Conference on Computational Geometry (CCCG 2014), Halifax, Nova Scotia, Canada (Aug 12, 2014).
V. KUSTERS
"Planar Packing of Binary Trees",
EuroGIGA Final Conference, Freie Universität Berlin, Germany (Feb 18, 2014).
"Column Planarity and Partial Simultaneous Geometric Embedding",
Graph Drawing 2014, University of Würzburg, Germany (Sep 25, 2014).
"Reconstructing Point Set Order Types from Radial Orderings",
25th International Symposium on Algorithms and Computation (ISAAC), Jeonju Traditional Culture Center, South Korea (Dec 15, 2014).
S. STICH
"Probabilistic Estimate Sequences",
TAO research seminar, INRIA Saclay,
Île-de-France, France (Mar 25, 2014).
"Probabilistic Estimate Sequences",
8th workshop on Theory of Randomized Search Heuristics (ThRaSH 2014)
Jena, Germany (Apr 4, 2014).
"Randomized Methods in Optimization",
8th Zurich Machine Learning and Data Science Meetup, Zurich, Switzerland (Sep 30, 2014).
M. SZEDLÁK
"Higher dimensional discrete Cheeger inequalites", Oberseminar, University of Cologne, Germany (May 7 2014).
A. THOMAS
"Recognizability & Long Cycles in USOs", COGA Breakfast Seminar, TU Berlin, Germany (Aug 26, 2014).
E. WELZL
"When Conflicting Constraints can be Resolved - the Local Lemma and Satisfiability ",
The Institute Colloquium, Institute of Science and Technology (IST Austria),
Klosterneuburg, Maria Gugging, Austria (Jan 13, 2014).
"The Counting of Crossing-Free Geometric Graphs - Algorithms and Combinatorics",
Pre-Workshop (WALCOM) School on Algorithms and Combinatorics,
IIT Chennai, India (Feb 10, 2014).
"The Counting of Crossing-Free Geometric Graphs - Algorithms and Combinatorics”,
Summit 240 Conference, Alfréd Rényi Institute of Mathematics,
Budapest, Hungary (Jul 10, 2014; invited plenary talk).
"The Counting of Crossing-Free Geometric Graphs - Algorithms and Combinatorics (Order on Order-Types)",
Colloquium in Honor of the 60th Birthday of Peter Gritzmann, Munich Technical University, Germany, (Dec 18, 2014).
M. WETTSTEIN
"Counting and Enumerating Crossing-free Perfect Matchings",
EuroGIGA Final Conference, Freie Universität Berlin, Germany (Feb 21, 2014).
"Counting and Enumerating Crossing-free Geometric Graphs",
Japanese-Swiss Workshop on Combinatorics and Computational Geometry, University of Tokyo, Japan (Jun 4, 2014).
"Counting and Enumerating Crossing-free Geometric Graphs",
30th Annual Symposium on Computational Geometry (SoCG), University of Kyoto, Japan (Jun 8, 2014).
K. FUKUDA
Editorial Board Member of
European J. Combinatorics, Computational Geometry: Theory and Applications,
Applied Mathematics Research eXpress.
B. GÄRTNER
Mitglied im Ausbildungs- und Beratungszentrum für Informatikunterricht ABZ und im Kinderlabor.
Mobilitätsberater des Departements Informatik
T. HERTLI
Teach. Assistance Coordinator.
Teach. Assistance Satisfiability of Boolean Formulas - Combinatorics and Algorithms (D-INFK) (Spring 14).
Teach. Assistance Informatik (D-MATH, D-PHYS) (Fall 14).
M. HOFFMANN
Informatik Koordinator.
Teach. Assistance Algorithms Lab (D-INFK) (Fall 14).
Member of the CGAL Editorial Board.
Program committee member of
V. KUSTERS
Coordinator Mittagsseminar.
Teach. Assistance Polynomials (D-INFK) (Spring 14).
Teach. Assistance Algorithms, Probability, and Computing (D-INFK) (Fall 14).
Best Presentation Award at Graph Drawing 2014.
J. MATOUŠEK
Elected member of the
Editorial Board member of
Program committee member of
Juror for the Richard-Rado-Prize 2014 of the Fachgruppe Diskrete Mathematik
of the German Mathematical Society (DMV), awarded at the Goethe-Universität
Frankfurt am Main, May 2014.
Co-winner of Best Paper Award at the 30th Annual Symposium on Computational Geometry (SoCG) (2014).
M. MILATZ
Teach. Assistance Algorithms, Probability, and Computing (D-INFK) (Fall 14).
S. STICH
Webmaster www-gremo (until Sep 30, 2014).
Program committee member of
M. SZEDLÁK
Teach. Assistance Polyhedral Computation (D-MATH) (Spring 14).
Teach. Assistance Algorithms, Probability, and Computing (D-INFK) (Fall 14).
A. THOMAS
Teach. Assistance Algorithms Lab (D-INFK) (Fall 14).
Teach. Assistance Informatik (D-MATH, D-PHYS) (Fall 14).
H. TYAGI
Webmaster www-gremo (since Oct 1, 2014).
Teach. Assistance Data Mining: Learning from Large Data Sets (D-INFK) (Spring 14).
Contact Assistant Geometry: Combinatorics and Algorithms (D-INFK) (Fall 14).
E. WELZL
Member of the board (deputy head) of the Department of Computer Science, ETH Zurich.
Editorial/Advisory Board member of
Member (chair, contact person) of selection committees for
Member of the
Program committee member of
Delegierter für Professorenwahlen an der ETH Zürich.
Elected as a corresponding member to the Austrian Academy of Sciences (OeAW).
M. WETTSTEIN
Contact Assistant Algorithms, Probability, and Computing (D-INFK) (Fall 14).