Table of Content

Graphen in und aus der Ebene

Sommersemester 2014
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 ,

1. Vorlesung, Mo. 14.4.2014 

  Ausblick auf Inhalte der VL.
  Grundlagen
     Zeichnungen, Kreuzungen, planare Graphen
     Der Jordansche Kurvensatz für polygonale Kurven
     Dualität für planar eingebettete Graphen
     Nicht-Planarität von K5
2. Vorlesung, Di. 15.4.2014 
    Satz von Whitney (eindeutige Einbettungen)
    Euler Formel (Beweis mit Euler-Kreisen)
    Gradlinige Zeichnungen existieren
        Induktion und Steinitz
  Charakterisierungen planarer Graphen
    Kuratowski - Wagner - Whitney - MacLane
3. Vorlesung, Di. 22.4.2014 
    Satz von Hanani-Tutte
        Beweis mit Kreuzungszählvektoren 
  Färben planarer Graphen
        6-Farben Beobachtung
        5-Farbensatz 
        Bemerkungen zum 4-Farbensatz
4. Vorlesung, Mo. 28.4.2014 
    4-Farbensatz
      Kempes Ansatz
        Unvermeidbare Konfigurationen
          Entladungsbeweise
          Reduzierbarkeit des 4-Rings
      Satz von Tait
        Ein nicht-hamiltonscher planarer 3-reg. Graph
5. Vorlesung, Di. 29.4.2014 
    Matchings
      Die Tutte-Berge Formel
      Satz von Petersen als Korollar
      Satz von Petersen mit Frinks Beweis
      Perfekte Matchings in bip. 3-reg Graphen
      Perfekte Matchings und Determinanten
6. Vorlesung, Mo. 5.5.2014 
    Listenfärbungen planarer Graphen
       5 ist bestm&oglich
    Steinberg Vermutung
       Ein Entladungsbeweis für 3-Färbbarkeit
         von planaren ohne k Kreise, 3 < k < 10.
7. Vorlesung, Di. 6.5.2014 
    Diskrete Geometrie
       Das Sylvester Problem
       Parabolische Dualität
       Allgemeine Dualität
       Melchiors Beweis
8. Vorlesung, Mo. 12.5.2014 
       Neuere Entwicklungen zum Sylvester Problem
       Magische Konfigurationen
9. Vorlesung, Di. 13.5.2014 
       Quasiplanare Graphen
         Ein Entladungsbeweis für die Kantenzahl
       Rot-Blaue Matchings
         Der Ham-Sandwich Satz
10. Vorlesung, Mo. 19.5.2014 (Guest lecturer: Piotr Micek) 
    Coloring geometric intersection graphs
       Introduction
       Squares and rectangles
       Families of pseudo-discs
11. Vorlesung, Di. 20.5.2014 (Guest lecturer: Piotr Micek) 
       The union complexity of families of pseudo-discs
          (an application of Hanani-Tutte)
       Triangle-free segment intersection graphs 
          * with high chromatic number
          * with small maximum independent set
12. Vorlesung, Mo. 26.5.2014 
     Durchschnittsgraphen von Segmenten
        Ein Approximationsalgorithmus für α
13. Vorlesung, Di. 27.5.2014 
     Durchschnittsgraphen von Rechtecken
        Ein Approximationsalgorithmus für α   
     Durchschnittsgraphen von Objekten mit linearer `union complexity'
        b-maximale Mengen liefern eine Approximation für α
14. Vorlesung, Mo. 2.6.2014 
        Eine randomisierte Approximation für α mittels LP 
     Durchschnittsgraphen von Kurven mit beschränkter Schnittzahl
        Ein Approximationsalgorithmus für α
15. Vorlesung, Di. 3.6.2014 
        Die Analyse des Approximationsalgorithmus
     Der Separator-Satz für planare Graphen
16. Vorlesung, Di. 10.6.2014 
     Unabhängige Mengen in planaren Graphen
        Rekursives Separieren
        Approximationsschema für Unabhängige Mengen
     Kreis-Kontakt-Darstellungen
17. Vorlesung, Mo. 16.6.2014 
     Der Satz von Koebe
        Radien implizieren Winkel, Winkelgleichungen
        Ein iteratives Verfahren
        Die Radien konvergieren
18. Vorlesung, Di. 17.6.2014 
     Orthogonale Kreispackungen
        Die Fehlerabbildung Ψ
        Analyse des Bildes Ψ(Δ)
     Ein Beweis des Separator-Theorems über Kreispackungen
19. Vorlesung, Mo. 23.6.2014 
     Federeinbettungen
        Energie als konvexe Funktion
        Berechnen der Federeinbettung
        Konvexe Zeichnungen 3-zush planarer Graphen
20. Vorlesung, Di. 24.6.2014 
     Auflösung einer Zeichnung
     Schnyder Woods
        Pfade und Regionen
        Zählen von Flächen in Regionen
        Die Dreiecke ∇e und ∇t
        Planare Zeichnung auf 2n-5 x 2n-5 Gitter
21. Vorlesung, Mo. 7.7.2014 
     Dreieckskontaktdarstellungen
       Konstruktion
       Varianten: rechtwinklig, gleichschenklig, gleichseitig.
     Segmentkontaktdarstellungen 
       Laman-Graphen 
       Henneberg-Erweiterungen
       Pseudotriangulierungen
22. Vorlesung, Di. 8.7.2014 
     Segmentkontaktdarstellungen von bipartiten planaren Graphen
       2-Orientierungen
       Separating Decompositions
       Bipolare Orientierungen 
       Planar bipolar und dual bipolar
       Segmentkontaktdarstellungen mit längsten Wegen
23. Vorlesung, Mo. 14.7.2014 
     Die Graphen einer Rechteckszerlegung
       Starke und schwache Äquivalenz
     3 Sätze zu Rechteckszerlegungen
       TS-Verband / Satz von He-Fusy / Schramm 
     Flächenuniversalität von schwachen Äquivalenzklassen  
       Eindeutigkeit
       Existenz
24. Vorlesung, Di. 15.7.2014 
     Flächenuniversalität und Einseitigkeit
     Orthogonale Kartogramme von Triangulierungen
     Transversale Strukturen
       Kompakte gradlinige Zeichnung aus TS
       Rechteckskontaktdarstellung aus TS
Back to main page.