Seminar Computational Geometry and Graph Drawing HS11
(263-4203-00L)

Contents

This seminar is held once a year and complements the courses Computational Geometry, Discrete Geometry, and Graph Drawing. 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 basic knowledge in (discrete and computational) geometry and graphs and algorithms is required. Thus, previous participation in some of the abovementioned courses (or similar courses) is strongly encouraged. It is also possible to take this seminar in parallel to the lecture Computational Geometry.

Dates

First meeting: Friday Sep 23rd 2011, 13:15-15:00, CAB G15.2.

The seminar will be held on the days listed below, from 11:00-12:00 (sine tempore), in CAB G15.2.

• Nov 4: Vincent Kusters (On Simultaneous Planar Graph Embeddings)
• Nov 18: Michael Hoffmann (Universal Sets of n Points for One-bend Drawings of Planar Graphs with n Vertices)
• Nov 25: Tobias Christ (Embedding Planar Graphs at Fixed Vertex Locations)
• Dec 2: Daniel Tschudi (On-Line Planarity Testing)
• Dec 9: Vladimir Serbinenko (Packing Trees into Planar Graphs)
• Dec 16: Manuel Wettstein (Drawing Binary Tanglegrams)

Proposed topics

1. Brass et al., On Simultaneous Planar Graph Embeddings, Computational Geometry: Theory and Applications 36, 117-130, 2007. [DOI]
2. Di Battista, Tamassia, On-Line Planarity Testing, SIAM J. Computing 25/5, 956-997, 1996. [DOI]
3. Di Giacomo, Liotta, Simultaneous Embedding of Outerplanar Graphs, Paths, and Cycles, Int. J. Computational Geometry 17/2, 139-160, 2007. [DOI]
4. Pach, Wenger, Embedding Planar Graphs at Fixed Vertex Locations, Graphs and Combinatorics 17, 717-728, 2001. [DOI]
5. Buchin et al., Drawing (Complete) Binary Tanglegrams Hardness, Approximation, Fixed-Parameter Tractability, Algorithmica, to appear. [DOI]
6. Everett, Lazard, Liotta, Wismath, Universal Sets of n Points for One-bend Drawings of Planar Graphs with n Vertices, Discrete and Computational Geometry 43, 272-288, 2010. [DOI]
7. Garcia, Hernando, Hurtado, Noy, Tejel, Packing Trees into Planar Graphs, J. Graph Theory 40/3, 172-181, 2002. [DOI]

Conditions

The seminar is held in English. Each talk is 45min. plus 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.

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.