max planck institut
mpii logoMinerva of the Max Planck Society

Seminar "Graphs on Surfaces" (WS 2012/13)

Basic Information

Seminar time Thursday 14-16
Seminar rooms E1.4 Room 023
Lecturers Matthias Mnich and Jens M. Schmidt
Audience Many graphs that appear in practice are graphs that can be embedded on surfaces, for example on the plane or on the torus. For several computational problems on graphs, the restriction to graphs that are embeddable on surfaces allows for more efficient algorithms than forgeneral graphs. This seminar aims at graph algorithms and parameterized complexity results that are specifically designed for graphs on surfaces. Talks should be given in English.
Credits You earn the usual 7 credit points for a seminar if you (i) give a regular presentation of the paper given to you, and (ii) write a summary. The presentation needs to be discussed with us at least one week before your scheduled talk in the seminar: please make an appointment by mail. This means in particular that you should have your presentation ready one week in advance, so that you can give a practice talk and we may discuss it. If you want credit for the course, please register by sending a short mail (here or here).
Lesson Plan
Datewho?TopicTalkSummary (drafts)
Nov 8Matthias + JensAssignment of research topics to students
Nov 22Presentation: Guilio Malavolta
Summary: Wenkai Dai
Kuratowski's Theorem and Whitney's Duality (Mohar, Thomassen)Talk 1.pdfSummary 1.pdf
Nov 29Presentation: Harry Zisopoulos
Summary: Stefan Bier
"Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus" (Dorn, Fomin, Thilikos)Talk 2.pdfSummary 2.pdf
Dec 6Presentation: Stefan Bier
Summary: Harry Zisopoulos
On the Number of Spanning Trees a Planar Graph can have (Buchin, Schulz)Talk 3.pdfSummary 3.pdf
Dec 13Presentation: Blaga Davidova
Summary: Guilio Malavolta
Faster minimum spanning trees in bounded genus graphs (Mares)Talk 4.pdfSummary 4.pdf
Dec 20Presentation: Wenkai Dai
Obtaining a planar graph by vertex deletion (Marx, Schlotter)Talk 5.pdf
Jan 10Presentation: Banasfsheh Sadry
The 5- and 4-Colour Theorem (Mohar, Thomassen)
Jan 17Presentation: Somnath
Summary: Somnath
Shortest Non-Crossing Walks in the Plane
Summary 7.pdf

Search MPII (type ? for help)