Table of Content

Graphen und Geometrie

Sommersemester 2012
Stefan Felsner und Kolja Knauer

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, Di. 9.4.2012 

  Grundlagen
     Zeichnungen, Kreuzungen, planare Graphen
     Der Jordansche Kurvensatz für polygonale Kurven
     Nicht-planarität von K5
     Euler Formel und Dualgraphen
     Satz von Whitney (unique embedding of a 3-connected planar graph)
2. Vorlesung, Mo. 15.4.2012 
  Klassische Sätze über planare Graphen
     Gradlinige Einbettungen
     Satz von Schnyder und Dimension von Inzidenzordnungen
3. Vorlesung, Di. 16.4.2012 
  Hanani-Tutte Theoreme
    Allgemeiner Hanani-Tutte mit Paritätsvektoren
    Schwacher Hanani-Tutte mit Kantenkontraktion
    Kreuzungsfreie gerade Kanten
4. Vorlesung, Mo. 23.4.2012 
  Graphen auf Flächen
    Flächen als topologische Räume
    2-Zell Einbettungen von Graphen
    Kanonische Darstellung von Flächen
5. Vorlesung, Di. 24.4.2012 
   Euler Characteristik und Orientierbarkeit
     Zwei Flächen sind homöomorph 
     genau dann wenn sie dieselbe Euler Characteristik und Orientierbarkeit haben.
6. Vorlesung, Mo. 30.4.2012 
   Kombinatorische Einbettungen
   Geschlecht eines Graphen
7. Vorlesung, Mo. 7.5.2012 
   Geschlecht Vollständiger Graphen
   Chromatische Zahl einer Fläche
   Heawoods Theorem
8. Vorlesung, Di. 8.5.2012 
   Federeinbettungen (Tutte drawings)
     Energiefunktion
     Diskrete Harmonic Functions
     GOOD Embeddings
9. Vorlesung, Mo. 14.5.2012 
   Resolution of drawings
   Schnyder woods
     Trees, Paths and Regions
     S-GOOD embeddings
10. Vorlesung, Di. 15.5.2012 
     S-GOOD embeddings yield planar drawings
       Empty-edge lemma
     Schnyder's drawing theorem
       Wedges of a vertex lemma
       Empty-face lemma
     Schnyder's dimension theorem
11. Vorlesung, Mo. 21.5.2012 
     Dimension of posets
       Lower bound for dimension of non-planar graphs
     Schnyder woods, Schnyder labelings and 3-orientations
       are equivalent for triangulations
     Schnyder woods and Schnyder labelings of 3-connected planar graphs
12. Vorlesung, Di. 22.5.2012 
     Convex drawings of 3-connected planar graphs
     Dual pairs of Schnyder woods
     Orthogonal surfaces and the Brightwell-Trotter Theorem
     More compact convex drawings
     Flips and Lattices
     --> Slides
13. Vorlesung, Di. 29.5.2012 
     Contact representations in general
     Triangle contact representations
     Cartograms (contact representations with prescribed areas)
     Cartograms with 4-sided polygons (darts)
14. Vorlesung, Mo. 4.6.2012 
    Planar bipolar orientations
       Vertex the face property
       Dual bipolar orientation
    Visibility representations
       Segments from ranks of vertices and faces
15. Vorlesung, Di. 5.6.2012 
       Segment contact representation of the angle graph
       Compact visibility representations
    Transversal structures
       Compact straight line drawings of 4-connected 
          inner triangulations of a 4-gon
16. Vorlesung, Mo 11.6.2012 
    Koebe's circle packing theorem
       Problem description and historical remarks
       The iteration: increasing radii of HIGH vertices 
       Radii remain bounded
       The layout fits
       Primal-dual circle packing
17. Vorlesung, Di. 12.6.2012 
     Squarings
       Bipolar orientations and separating decompositions
       A flow from counting trees
       Rotation-free flow and dual flow
       Squarings from a linear system of equations
18. Vorlesung, Mo. 18.6.2012 
   Crossing numbers
      Crossing number versus rectilinear crossing number
      The crossing lemma
        Optimality up to the constant
19. Vorlesung, Di. 19.6.2012 
      Crossing numbers of complete graphs
        The randomized Moon construction on the sphere
        A lower bound for the rectilinear crossing number
          Connection with k-edges
      The edge number of 1-reduced drawings
20. Vorlesung, Mo. 25.6.2012 
      Posets, Lattices, and distributive Lattices.
       Birkhoff's Theorem a.k.a. The Fundamental Theorem of Finite Distributive Lattices
21. Vorlesung, Di. 26.6.2012 
      Embedding Distributive Lattices into the Integer Lattice
       Embeddings as Chain-Partitioned Posets and Arc-Colored Digraphs
22. Vorlesung, Mo. 2.7.2012 
      The Distributive Lattice of α-Orientations of a Planar Graph
      Tensions and Vertex-Potentials
23. Vorlesung, Di. 3.7.2012 
      The Distributive Lattice of Tensions and Potentials of a Digraph
      Distributive Polyhedra
24. Vorlesung, Mo. 9.7.2012 
     Geometric Intersection Graphs
      STRING-Graphs
       Planar Grahs
       Cocomparability Graphs
25. Vorlesung, Di. 10.7.2012 
     Coloring Geometric Intersection Graphs
      Axis-alligned rectangles
      Segement-graphs
     Coloring Geometric Hypergraphs
      Bottomless rectangles
Back to main page.