Seminar Geometry: Combinatorics and Algorithms FS20 (263-4203-00L)

Bernd Gärtner,	CAB G31.1,	Tel: 044-632 70 26,	lastname@inf.ethz.ch
Michael Hoffmann,	CAB G33.1,	Tel: 044-632 73 90,	lastname@inf.ethz.ch
Emo Welzl,	CAB G39.2,	Tel: 044-632 73 70,	firstname@inf.ethz.ch
Manuel Wettstein,	CAB G38,	Tel: 044-632 32 22,	firstname.lastname@inf.ethz.ch

Contents

This seminar is held once a year and complements the course Geometry: Combinatorics & Algorithms. Students of the seminar will present original research papers, some classic and some of them very recent. The seminar is a good preparation for a master, diploma, or semester thesis in the area.

To attend the seminar, some background in (discrete and computational) geometry and in graphs and algorithms is required. Thus, previous participation in the course "Geometry: Combinatorics & Algorithms" is a prerequisite.

Dates

First meeting: Friday Feb 21st 2020, 13:15, CAB G15.2.

Topic and Papers

The title of the seminar is Edge flips in plane graphs.
(To be able to access some of the papers linked below, you may need to be within the ETH network, e.g. via VPN.)

Schedule

• Read the following article: Satyan L. Devadoss. Giving Good Talks. Notices AMS 66, 1647-1650, 2019.
• April 24, 2020, 13:15-13:45: Tim Taubner
  David Eppstein. Happy endings for flip graphs. J. Comput. Geom. 1(1): 3-28, 2010. [DOI]
• April 24, 2020, 14:00-14:30: Meghana M. Reddy
  Javier Cano, José Miguel Díaz-Báñez, Clemens Huemer, and Jorge Urrutia. The Edge Rotation Graph. Graph Combin. 29:1207-129, 2013. [DOI]
• April 24, 2020, 15:00-15:30: Daniel Bertschinger
  Michael Hoffmann, Micha Sharir, Adam Sheffer, Csaba D. Tóth, and Emo Welzl. Counting Plane Graphs: Flippability and Its Applications. Thirty Essays on Geometric Graph Theory, 303-325, 2013. [DOI]
• May 8, 2020, 13:15-14:00: Marco Kräuchi
  Ferran Hurtado, Marc Noy, and Jorge Urrutia. Flipping edges in triangulations. Discrete Comput. Geom. 22(3): 333-346, 1999. [DOI]
• May 8, 2020, 14:45-15:30: Valentin Stoppiello
  Anna Lubiw, Zuzana Masárová, and Uli Wagner. A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations. Discrete Comput. Geom. 61(4): 880-898, 2019. [DOI]
• May 15, 2020, 13:15-14:00: Alexandre Krattinger
  Alexander Pilz. Flip distance between triangulations of a planar point set is APX-hard. Comput. Geom. Theory Appl. 47(5): 589-604, 2014. [DOI]
• May 15, 2020, 14:45-15:30: Jan Schilliger
  Iyad Kanj, Eric Sedgwick, and Ge Xia. Computing the Flip Distance Between Triangulations. Discrete Comput. Geom. 58: 313-344, 2017. [DOI]

All talks are held online using Zoom. Details are available to the participants and on request only.

Conditions

The seminar is held in English. Each talk is 45min. plus about 15min. discussion.
Every participant is expected to read, understand, and elaborate on a selected research paper. To this end, (s)he should give a 45-min. presentation about the paper. The process includes

1. getting an overview of the related literature;
2. understanding and working out the background/motivation: why and where are the questions addressed relevant?
3. understanding the contents of the paper in all details;
4. selecting parts suitable for the presentation;
5. presenting the selected parts in such a way that an audience with some basic background in geometry and graph theory can easily understand and appreciate it.

For more details, please refer to our guidelines for seminar talks. A number of additional related documents from different authors (both in English and German) are linked to from here.

A successful participation in the seminar requires the following:

1. a rehearsal talk, to be given in front of your supervisor at least one week prior to the plenary talk;
2. a satisfactory plenary talk;
3. attendance at all other talks.

---

Last modified: Mon Apr 20 12:09:21 CET 2020 by Michael Hoffmann.

Valid HTML5