Seminar Geometry: Combinatorics and Algorithms FS19 (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
Chih-Hung Liu,	CAB G19.3,	Tel: 044-632 74 01,	firstname.lastname@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 22nd 2019, 13:15, CAB G15.2.

Schedule

• April 12, 2019, 13:15-14:00: Nicolas Grelier
  K. Knauer, P. Micek, and T. Ueckerdt. The queue-number of posets of bounded width or height. In Proc. 23rd Internat. Sympos. Graph Drawing Network Visualization, volume 11282 of Lecture Notes Comput. Sci., pages 200–212. Springer, 2018. [PDF]
• May 10, 2019, 13:15-14:00: Hung Hoang
  V. Dujmović and F. Frati. Stack and queue layouts via layered separators. J. Graph Algorithms Appl., 22(1):88–99, 2018. [PDF]
• May 10, 2019, 14:30-15:15: Emanuel Seemann
  J. M. Alam, M. A. Bekos, M. Gronemann, M. Kaufmann, and S. Pupyrev. Queue layouts of planar 3-trees. In Proc. 23rd Internat. Sympos. Graph Drawing Network Visualization, volume 11282 of Lecture Notes Comput. Sci., pages 213–226. Springer, 2018. [PDF]
• May 17, 2019, 13:15-14:00: Michael Frey
  M. J. Bannister, W. E. Devanny, V. Dujmović, D. Eppstein, and D. R. Wood. Track layouts, layered path decompositions, and leveled planarity. Algorithmica, to appear, 2019. [PDF]
• May 17, 2019, 14:30-15:15: Robert Meier
  E. de Klerk, D. V. Pasechnik, and G. Salazar. Book drawings of complete bipartite graphs. Discrete Appl. Math., 167:80–93, 2014. [PDF]
• May 24, 2019, 13:15-14:00: Nathanael Neukom
  M. Yannakakis. Embedding planar graphs in four pages. J. Comput. Syst. Sci., 38(1):36–67, 1989. [PDF]
• May 24, 2019, 14:30-15:15: Zeyu Wang
  S. M. Malitz. Genus g graphs have pagenumber O(√g). J. Algorithms, 17:85–109, 1994. [PDF]

All talks in CAB G15.2.

Topic and Papers

The title of the seminar is Graph Layouts: Stacks, Queues and Tracks.
(To be able to access some of the papers linked below, you may need to be within the ETH network, e.g. via VPN.)

• V. Dujmović. Graph layouts via layered separators. J. Combin. Theory Ser. B, 110:79–89, 2015. [PDF]
• J. L. Ganley and L. S. Heath. The pagenumber of k-trees is O(k). Discrete Appl. Math., 109(3):215–221, 2001. [PDF]
• L. S. Heath, F. T. Leighton, and A. L. Rosenberg. Comparing queues and stacks as mechanisms for laying out graphs. SIAM J. Discrete Math., 5(3):398–412, 1992. [PDF]
• S.-H. Hong and H. Nagamochi. Simpler algorithms for testing two-page book embedding of partitioned graphs. Theoret. Comput. Sci., 725:79–98, 2018. [PDF]

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: Thu Feb 28 23:59:52 CET 2019 by Michael Hoffmann.

Valid HTML5