Table of Content

Planar Graphs

Sommersemester 2008
Stefan Felsner

1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 ,

1. Vorlesung, Mo. 14.4.2008 

  Grundlagen
     Zeichnungen, Kreuzungen, planare Graphen
     Existenz polygonaler Zeichnungen
     Der Jordansche Kurvensatz für polygonale Kurven
     Nicht-planarität von K5 und K3,3
2. Vorlesung, Di. 15.4.2008 
     Bäume
     Blöcke
     Zusammenhang
        Ohren-Zerlegung
     Die Euler Formel für 2-zush. planare Graphen
3. Vorlesung, Mo. 21.4.2008 
   Charakterisierungen
     Satz von Kuratowski
        Dekompositionslemma für 3-zush. Graphen
4. Vorlesung, Di. 22.4.2008 
        Kuratowski-Unterteilungen und Kontraktionen
        Konvexe Einbettungen für K5-undK3,3-freie Graphen
           Erweiterung planarer Graphen zu Triangulierungen
           Triangulierungen sind 3-zush.
           Gradlinige Zeichnungen
5. Vorlesung, Mo. 28.4.2008 
     Kreise, Schnitte, Vektorräume
        Zyklenraum
        Schnittraum
        Kreis-Schnitt-Baum Theorem
        Mac Lane Kriterium: 2-Basis
6. Vorlesung, Di. 29.4.2008 
      Gerade Zeichnungen
         Manipulieren von Zeichnungen
         Kreuzungs-Paritäts-Vektoren
         Hanani-Tutte Kriterium
      Brücken an Kreisen
         Überlappungsrelationen
         Tutte-Thomassen-Williamson Kriterium
7. Vorlesung, Di. 13.5.2008 
     Dimension und Planarität
        Partielle Ordnungen, lineare Erweiterungen
        Der generische LinExt Algorithmus
        P als Durchschnitt seien lin. Erw.
        Dimension - Durchschnitts und Produktdefinition
        dim(P - x) \geq dim(P) -1
8. Vorlesung, Mo. 19.5.2008 
        C Kette, dim(P - C) \geq dim(P) -2
        dim(P) \leq weite(P)
        Dimension von Inzidenzordnungen von Kreisen und Sternen
        Ein Dimensionsbegriff für Graphen
        Dimension vollständiger Graphen
        dim(G) \leq 3 impliziert planar
9. Vorlesung, Di. 20.5.2008 
        Schnyder Woods
        Die Regionen eines Knotens
        Ein 3-Realizer für planare Triangulierungen
        Winkelfärbungen und 3-Orientierungen
        Existenz von schnyder Woods
        Zeichnungen auf dem (f-1)x(f-1) Gitter
10. Vorlesung, Mo. 26.5.2008 
     Dualität
        Geometrische Dualität 
           Kreise und Schnitte         
        Kombinatorische Dualität
           Satz von Whitney
     Beweise für die Euler Formel
        Duale Bäume
        Induktion über Kantenzahl
        Verschieben von Ladungen
11. Vorlesung, Di. 27.5.2008 
        Winkelsummen
        Picks Theorem
     Planaritäts Tests
        Überblick
        Erinnerung, H-Brücken und Konflikte
        Ein quadratischer Algorithmus
           Korrektheit
12. Vorlesung, Mo. 02.6.2008 
        Planaritäts in Linearzeit
           (Grundlegende Ideen)
           Umgekehrte DFS Nummerierung
           Wald der Bikomps
           Erweiterbarkeitskriterien mit A- und Z-Knoten
           PC-Bäume für die Bikomp-Bäume
13. Vorlesung, Di. 03.6.2008 
     Planar Separator Theorem
        Kleine balancierte Separatoren und Divide & Conquer
        Ideen des Lipton-Tarjan Beweises
        Beweis von Alon-Seymour-Thomas
14. Vorlesung, Mo. 09.6.2008 
        Anwendung: Matching
     Kreispackungsdarstellungen
        Radien fuer Triangulierungen
        Zusammensetzen der Dreiecke
15. Vorlesung, Di. 10.6.2008 
        Primal-Dual Kreispackungsdarstellungen
          Kites
          Der Simplex der Radien Σ
          Das Fehlerpolytop Π
16. Vorlesung, Mo. 16.6.2008 
          Die Abb Ψ : Σ -> Π
          Ψ ist surjektiv
        Planar Separator Theorem und Kreispackungsdarstellungen
18. Vorlesung, Mo. 23.6.2008 
     Federeinbettungen
        Energie
          Eindeutigkeit der Lösung
        Linearisierung
          Diskrete harmonische Funktionen
19. Vorlesung, Di. 24.6.2008 
       Der planare Fall
         "Gute" Einbettungen
     Bipolare Orientierungen
       Lokale Bedingungen
       Die duale Orientierung
20. Vorlesung, Mo. 30.6.2008 
       Primal-duale Sichtbarkeitsdarstellung
       Zeichnungen mit einem Knick je Kante
       Planare s-t Graphen und 2-dimensionale Ordnungen
21. Vorlesung, Di. 1.7.2008 
     Primal-duale Sichtbarkeitsdarstellung II
       Kantengerwichtung: Zählen von Bämen
       Flußerhaltung
       Duale Flußerhaltung (Kreisflußgesetz)
       Potentiale und die Quadratdarstellung
22. Vorlesung, Mo. 7.7.2008 
     Transversale Strukturen
       Zerlegung in zwei bipolare Orientierungen
       Zählen in roten und im blauen Graphen: Zeichnung
       Größe der Zeichnung
       Existenz von Transversale Strukturen
         Bijektion mit (4,1)-Orientierungen
         Die Hall Bedingung
23. Vorlesung, Di. 8.7.2008 
     Zählen von bipolaren Orientierungen
       Separating Decompositions
       Bucheinbettung von Q mit einer SD
       Alternierende Einbettung von Bämen
       Bijektion: Alternierende - Binäre Bäme
       Codierung von Bämen: Fingerprint und Innerprint
       Zählen mittels Gessel-Viennot
24. Vorlesung, Mo. 14.7.2008 
     Fries Muster und Zählen von Matchings
       Fries Muster einer Triangulierung des n-gons
       Fries-Zahlen und Matchings
25. Vorlesung, Di. 15.7.2008 
      Färbung planarer Graphen
        Heawoods 5-Farben Satz
        Kempes 4-Farben "Beweis"
        Plan für den 4-Farben Satz
          Unvermeidbare Konfigurationen
            Entladung
          Reduzierbarkeit
            Der 4-Ring

Back to main page.