Announcements

Guten Abend,

ein kleiner Nachtrag zur VL 11 (Beyond Planarity) vom letzten Freitag. Hier stand auf Folie 13–2, dass die 1-planare Kreuzungszahl immer höchstens n − 2 ist. Die Begründung folgt aus dem Beweis von Satz 1: man färbt in einer 1-planaren Zeichnung jede nicht gekreuzte Kante rot und jedes Paar aus gekreuzten Kanten blau und grün. Wie wir zuvor argumentieren, gibt es höchstens n − 2 grüne (und damit auch blaue) Kanten und entsprechend auch höchstens so viele Kreuzungen. Als Erklärung ist jetzt ein Verweis auf diese Färbung auf der Folie ergänzt.

Außerdem ein kleiner Nachtrag zur VL 9 (Partial Visibility Representation Extension). Hier stand auf Folie 6–21 als Anmerkung, dass es NP-vollständig ist, für einen gerichteten azyklischen planaren Graphen zu entscheiden, ob er eine Weak-Bar-Visibility-Repräsentation zulässt, weil dies dem Problem entspricht, zu entscheiden, ob eine gegebener Graph aufwärtsplanar ist. Leider war dies nur schwer als Anmerkung zu erkennen (und konnte damit für Verwirrung sorgen) und außerdem wurden Bar-Visibility-Repräsentationen nicht ordentlich für gerichtete Graphen definiert. Zur Klarstellung habe ich jetzt eine neue Folie zugefügt, die Bar-Visibility-Repräsentationen für gerichtete Graphen definiert und diese Anmerkung behandelt.

Viele Grüße und schönen Abend,
Johannes

PS: Ich werde in dieser Woche noch eine wichtige Ankündigung zur mündlichen Prüfung machen. Bitte prüft hierfür regelmäßig eure E-Mails/schaut ins Forum.