Seminar Geometry: Combinatorics and Algorithms FS19 (263-4203-00L)
||Tel: 044-632 70 26,
||Tel: 044-632 73 90,
||Tel: 044-632 74 01,
||Tel: 044-632 32 22,
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.
: Friday Feb 22nd 2019, 13:15,
- 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]
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
- getting an overview of the related literature;
- understanding and working out the background/motivation:
why and where are the questions addressed relevant?
- understanding the contents of the paper in all details;
- selecting parts suitable for the presentation;
- 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:
- a rehearsal talk, to be given in front of your supervisor
at least one week prior to the plenary talk;
- a satisfactory plenary talk;
- attendance at all other talks.