Geometrische und Topologische Graphen -- Sommersemester 2007

Seminar
Ausgewählte Kapitel der Graphentheorie: Geometrische und Topologische Graphen

Sommersemester 2007
Prof. Stefan Felsner
Sprechstunde n.V.

LV-Nr.: 0230 L 316

$Zeichnung$

TERMIN: 15.6. und 22.6 jeweils ab 12:30. MA645

Thema:

Ein topologischer Graph ist ein Graph der mit einer Zeichnung in die Ebene gegeben ist. Die Knoten des Graphen sind Punkte in der Ebene, Kanten sind durch Kurven (Jordanbögen) gegeben.
Ein geometrischer Graph ist ein topologischer Graph dessen Kanten gradlinig sind, das heisst die Kanten sind Strecken zwischen den Endpunkten.
Die im Seminar behandelten Fragestellungen sind weitgehend extremaler Art, z.B. wieviele Kanten kann ein geometrischer Graph mit n Knoten haben wenn sich keine drei Kanten paarweise schneiden?

Literatur:

Als Grundlage für die Vortraäge werden Originalarbeiten ausgegeben. Einführungen in die Theorie der geometrischen und topologischen Graphen gibt es in

J. Pach, P. Agarwal, Combinatorial Geometry. Wiley (1995).
S. Felsner, Geometric Graphs and Arrangements. Vieweg (2003).
Das erste Kapitel des Buches: GG+A Kapitel 1 (als PostScript)

Vorträge:

Thema	Vortragende
Competitive on-line routing in geometric graphs (Bose/Morin)	Robert Luce
The maximum number of edges in quasi-planar graphs (Ackerman/Tardos)	Tanja Massoth
Distinguishing geometric graphs (Albertson/Boutin)	Gesine Koch
Pointes and colored binary encompassing trees (Hoffmann/Toth)	Eannon Coughlan
Unavoidable Configurations in Complete topological Graphs (Pach/Toth)	Michal Starosta
Geometric graphs with no three disjoint edges (Cerny)	Joaddin Göbel

Termine:

15.6. und 22.6 jeweils ab 12:30.

Zielgruppe:

Studentinnen und Studenten der Mathematik, Techno- und Wirtschaftsmathematik im Hauptstudium.
Dieses Seminar wird im Rahmen des Studienschwerpunkts Diskrete Strukturen empfohlen.

Zuletzt bearbeitet April 2007