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

Luis Barba,	CAB G33.3,	Tel: 044-632 77 96,	firstname.lastname@inf.ethz.ch
Bernd Gärtner,	CAB G32.2,	Tel: 044-632 70 26,	lastname@inf.ethz.ch
Michael Hoffmann,	CAB G33.1,	Tel: 044-632 73 90,	lastname@inf.ethz.ch
Alexander Pilz,	CAB G38,	Tel: 044-632 04 34,	firstname.lastname@inf.ethz.ch
Emo Welzl,	CAB G39.2,	Tel: 044-632 73 70,	firstname@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 24th 2017, 13:15, CAB G15.2.

Schedule

• April 28, 2017, 13:15-14:00: Patrick Schnider
  García et al.: Geometric Biplane Graphs I: Maximal Graphs, Graphs and Combinatorics 31,2: 407-425, 2015. [DOI]
  García et al.: Geometric Biplane Graphs II: Graph Augmentation, Graphs and Combinatorics 31,2: 427-452, 2015. [DOI]
• April 28, 2017, 14:30-15:15: Cyril Frei
  David Eppstein, Marc van Kreveld, Elena Mumford, and Bettina Speckmann, Edges and Switches, Tunnels and Bridges, Computational Geometry: Theory and Applications 42: 790-802, 2009. [DOI]
• May 5, 2017, 13:15-14:00: Stefan Lochau
  Eyal Ackerman, A note on 1-planar graphs, Discrete Applied Mathematics 175: 104-108, 2014. [DOI]
• May 5, 2017, 14:30-15:15: Roland Schmid
  Eyal Ackerman and Gábor Tardos, On the maximum number of edges in quasi-planar graphs, Journal of Combinatorial Theory, Ser. A 114,3: 563-571, 2007. [DOI]

All talks in CAB G15.2.

Topic and Papers

The title of the seminar is Beyond Planarity: How to control crossings.

Planar graphs are nice because they can be drawn on a screen or on a sheet of paper so that no two edges cross. Edge crossings increase the visual complexity of a drawing because one has to figure out how the four curves that leave a crossing are paired up. Therefore, it is desirable to avoid edge crossings in a drawing. However, not all graphs are planar. So what can we do if edge crossings are unavoidable? What are reasonable models to restrict the number of crossings or the type of crossings in a drawing? Which graphs allow such a restricted drawing? Which combinatorial properties can be derived from such a geometric restriction?

• János Pach and Géza Tóth, Graphs drawn with few crossings per edge, Combinatorica 17: 427-439, 1997. [DOI]
• Seok-Hee Hong, Peter Eades, Giuseppe Liotta, and Sheung-Hung Poon, Fáry’s Theorem for 1-planar graphs, Computing and Combinatorics (COCOON 2012), LNCS Vol. 7434: 335-346, 2012. [DOI] and
  Carsten Thomassen, Rectilinear drawings of graphs, Journal of Graph Theory 12,3: 335-341, 1988. [DOI]
• Seok-Hee Hong and Hiroshi Nagamochi, Re-embedding a 1-plane graph into a straight-line drawing in linear time, Graph Drawing and Network Visualization (GD 2016), LNCS Vol. 9801: 321-334, 2016. [DOI]
• Eyal Ackerman, On the maximum number of edges in topological graphs with no four pairwise crossing edges, Discrete & Computational Geometry 41,3: 365-375, 2009. [DOI]
• Andrew Suk and Bartosz Walczak, New bounds on the maximum number of edges in k-quasi-planar graphs, Computational Geometry: Theory and Applications 50: 24-33, 2015. [DOI]
• Walter Didimo, Peter Eades, and Giuseppe Liotta: Drawing graphs with right angle crossings, Theoretical Computer Science 39: 5156-5166, 2011. [DOI]
• Carla Binucci, Emilio Di Giacomo, Walter Didimo, Fabrizio Montecchiani, Maurizio Patrignani, Antonios Symvonis, Ioannis G. Tollis, Fan-planarity: Properties and complexity, Theoretical Computer Science 589: 76-86, 2015. [DOI]

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: Wed Mar 1 17:26:41 CET 2017 by Michael Hoffmann.