Table of Content

Topologische Graphentheorie und Kreuzungszahlen (Diskrete Strukturen III)

Sommersemester 2020
Stefan Felsner

  Besprechung des Formats

  Basics (p 3-10)

  Crossing Lemma (p 11,12)
  Appendix A (Basics of Topological Graph Theory)

  The Parity Theorem (p 13)

  Complete Bipartite Graphs - Zarankiewicz (p 14-20)

  Can drawings (Dosenzeichnungen) of complete graphs (p 21-23)

  Hill drawings of complete graphs (p 24)
   handwritte notes.

  Asymptotic behavior of cr(K_n) and Moon construction (p 25-30)
   Moon construction.
  (mit technischen Problemen)   

  Exercises up to 1.12 

   Rotations and weak isomorphism
   Enumeration of weak iso classes of complete drawings (p 33-36)

   Enumeration of iso classes of complete drawings (p 36-37)

   Theorem 2.5 uncrossed edges (p 38)
  2 Übungsaufgaben.
  Notizen Thm 2.4 und 2.5.
  Kyncl Artikel zu Enumeration.

  Harborth-Mengersen Konstruktion für h(n)=0
  Thm 2.6 - Kreuzungsfreie Kanten in Doppelsternen

  Leere Dreiecke (Thm 2.7), kreuzungsfreie Subzeichnungen (2.8) und Monotonisierung
  Notizen  

  Disjunkte Kanten in x-monotonen Zeichnungen und Zeichnungen des K_n 
  Notizen

  Die Kreuzungszakl der Produkte (Stern)x(Pfad) [Theorem 2.11]
  Notizen

  Uebungen 2.3, 2.4, 2.5 
  K6 zu UE 2.5

Die Kreuzungszahl von Produkten von Kreisen: C3xC3 / C3xCn / C4xC4.
  Notizen

Die Kreuzungszahl von C4xCn.
  Notizen

 Untere Schranke an die Kreuzungszahl von CmxCn und Hyperwürfel.
  Notizen

 Kreuzungskritische Graphen
  Notizen

  Kantenzahl kreuzungskritischer Graphen

  Übungsaufgaben zu Kap. 2
  Kreuzungszahl und branch-width

  Kreuzungszahl und cut-width

  Kreuzungszahl dünner Zufallsgraphen
  Embedding and Congestion

  Kreuzungszahl Q_n (untere Schranke)
  Skewness

  Cr und Kanten-Cr, Thickness und Chromatische Zahl

  Kreuzungszahl und Geschlecht von Graphen

  Kreiskriterium für die Sphäre
  Crossing Lemma für Flächen
  Notizen

  Crossing Sequences
    Gewichtete Graphen, Graphen mit Patches   

  Disjunkte Graphen in der projektiven Ebene
    Satz von Lins, Satz von Okamura Seymour

  Minoren und Kreuzungszahlen

 Uebungen zu Kapitel 3

 NP-Vollständigkeit von cr und skewness

 Kreuzungen und Rotationen
  Notizen 

  Fortsetzung: Kreuzungen und Rotationen
  Der cyclic order graph

  (Kyncl's Theorem) Erkennung zulässiger Rotationssysteme

  (Gioan's Thorem) Schwache Äquivalenz und Dreiecksflips

  Die gradlinige Kreuzungszahl

  Pseudogeradenarrangements und
  Konvexität in Zeichnungen des Kn
  Notizen

  Übungen zu Kapitel 4.

  Pseudolineare Kreuzungszahl, 
  ExistR-Vollständigkeit der gradlinigen Kreuzungszahl

  Zählen gradliniger Zeichnungen des Kn
  (Warren's Theorem: bound for number of sign patterns)

  Crossing constant and Sylvester's four point Problemen
  Konstruktionen gradliniger Zeichnungen mit wenig Kreuzungen

  Die untere Schranke k-Kanten
  Schranken für (< k)-Kanten
  Ergänzendes Material:   Folien G. Salazar 2012

  Die Hill Schranke für gradlinige Zeichnungen
  Gradlinige Kreuzungszahl vom K8 - bishellable drawings

  Übungen zu Kapitel 5.

  Gradlinige Zeichnungen von Hyperwürfeln
  Die lokale Kreuzungszahl 

   Verbessertes Crossing Lemma
   Asymptotische lokale Kreuzungszahl

   Lokale Kreuzungszahl auf Flächen
   Notizen

   Ringels 7-Färbungssatz
   NP-Vollständigkeit der Erkennung 1-planarer Graphen

   Thomassens Charakterisierung von streckbaren 1-planaren Graphen
   Notizen

   Die Kantenzahl von k-quasiplanaren Graphen (O(n\log^{2k-4}n))

   Die Kantenzahl von 3-quasiplanaren Graphen \le 10n-20
   Notizen

  Page-number (book-thickness): basics, planar graphs
  The Malitz bound

   Die Page-number von K_n, K_m,n und Q_n
   Kodierung konvexer Zeichnungen

   Hanani-Tutte Theorem
   2 Beweise: kontraktionen / topologisch 

   Strong Hanani-Tutte Theorem via lineraer Algebra
   Notizen

   Maximum crossing number