Geometrische Graphen und Arrangements

• Dozent: Alexander Wolff
• Betreuung der Übung: PD Dr. Martin Nöllenburg
• Vorlesung: wöchentlich montags 11:30-13:00 Uhr im SR 301 (Informatik-Gebäude 50.34)
• Übung: 14-tägig donnerstags 14:00-15:30 Uhr im SR 301 (Informatik-Gebäude 50.34)

Wir werden im Laufe des Semesters in Abhängigkeit der Vorkenntnisse der Hörer eine Teilmenge der folgenden Themen behandeln:

1. Wieviele Kanten kann ein Graph mit n Knoten haben, der eine bestimmte Eigenschaft erfüllt (z.B. keine k-Clique zu besitzen)? Das ist ein typisches Turán-Problem und damit ein Problem der extremalen Graphentheorie.
2. Wie kann man dreifach-zusammenhängende planare Graphen so zeichnen, dass jede Facette konvex ist? Dabei helfen sogenannte Schnyder-Wälder.
3. Gegeben ein (nicht-planarer) Graph, wieviele Kreuzungen muss man akzeptieren, wenn man ihn in der Ebene zeichnen will? Das Kreuzungslemma liefert eine obere Schranke.
4. Gegeben eine Menge P von n Punkten in der Ebene. Eine k-Menge von P ist eine Teilmenge der Kardinalität k von P, die sich durch eine Gerade von ihrem Komplement trennen lässt. Wir suchen asymptotische Schranken für die Anzahl dieser Mengen.
5. Wieviele Dreiecke enthält ein Arrangement von Geraden?
6. Arragements von Pseudogeraden haben gegenüber Geraden-Arrangements den Vorzug, dass sie sich leicht durch andere kombinatorische Objekte codieren lassen. Wir stellen einige kombinatorische Repräsentationen vor und beweisen Zusammenhänge zwischen ihnen.
7. Gegeben zwei Triangulierungen derselben Punktemenge, wie oft muss man die Flipp-Operation anwenden, um eine Triangulierung in die andere zu überführen? Bei dieser Operation werden zwei benachbarte Dreiecke, die ein konvexes Viereck bilden, durch zwei andere Dreiecke ersetzt, die dasselbe Viereck bilden.
8. Wir verallgemeinern die Flipp-Operation auf Pseudo-Triangulierungen und zeigen, dass man damit ebenfalls eine Pseudo-Triangulierung in jede andere überführen kann. Dieses Resultat findet Anwendung beim Falten von Zollstöcken. Wir stellen den Zusammenhang zwischen Pseudo-Triangulierungen und einer Unterklasse der planaren starren Graphen her.

Die Vorlesung wendet sich an Hörer im Hauptstudium. Voraussetzung für die Teilnahme ist die Kenntnis der wichtigsten Begriffe aus der Graphentheorie (Zusammenhang, Breiten- und Tiefensuche, Spannbäume, Matchings) und der Komplexitätstheorie (Groß-Oh-Notation!), die im Grundstudium eingeführt wurden.

Die Vorlesung wird sich relativ eng an das Buch [1] halten. Bücher, die sich mit verwandten Themen auseinandersetzen, sind [2,3,4,5].

Zusätzliches Material zur Vorlesung:

1. Kapitel 7.3 in Schrijvers Skript (Posets)
2. Seite zu „Schnittlingen“ www.thrackle.org
3. Gegenüberstellung Schnyder-Beschriftung - Schnyder-Hain zum Ausfüllen [pdf] (Vorlesung vom 21.11.2005)
4. Gegenüberstellung Schnyder-Hain - Schnyder-DAG zum Ausfüllen [pdf] (Vorlesung vom 28.11.2005)
5. Gegenüberstellung geodätische und konvexe Zeichnung [pdf] (Vorlesung vom 19.12.2005)
6. Fest-Parameter-Algorithmen für aufspannende Bäume mit wenigen Kreuzungen in topologischen Graphen [pdf] (letzte Vorlesung)

1. Stefan Felsner. Geometric Graphs and Arrangements. Vieweg-Verlag, 2004.
2. Herbert Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge University Press, 2001.
3. János Pach and Pankaj K. Agarwal. Combinatorial Geomtry. John Wiley & Sons, 1995.
4. Jirí Matousek. Lectures on Discrete Geometry, volume 212 of Graduate Texts in Mathematics. Springer-Verlag, 2002.
5. Günter M. Ziegler. Lectures on Polytopes, volume 152 of Graduate Texts in Mathematics. Springer-Verlag, 1994.