Logo der Fakultät Logo LG Theoretische Informatik
 

Abschlussarbeit

Illustration

Analyse der Dichte von PPC Graphen

Status: Themenangebot
Beschreibung: Ein Graph ist ein PPC Graph der sich so zeichnen lässt, dass wenn immer sich zwei Kanten kreuzen, zwei Endpunkte dieses Kantenpaares durch eine weitere Kante verbunden sind, die selbst keine Kreuzungen besitzt. Man weiß, dass ein PPC Graphen mit n Knoten maximal 699n Kanten haben kann. Es gibt aber auch PPC Graphen mit knapp 9n Kanten. Ziel der Arbeit ist es, die Beweise dieser Schranken zu reproduzieren und dabei schärfere Abschätzungen vorzunehmen, um damit die bekannten Schranken zu verbessern.
Christoph Doppelbauer | 30.09.2016
FernUni-Logo FernUniversität in Hagen, LG Theoretische Informatik, 58084 Hagen