Christoph Peters

Algorithmen für gerade Triangulierungen spezieller planarer Graphen

Betreuer: Klaus Kriegel
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 31.01.2017

Kurzbeschreibung

Wir beschäftigen uns mit geraden Triangulierungen von 3-zusammenhängenden planaren Graphen. Dabei heißt eine Triangulierung gerade, falls sie ausschließlich gerade Knotengrade hat. Wir untersuchen zunächst 3-zusammenhängende bipartite planare Graphen und übertragen dann die gewonnenen Erkenntnisse auf sogenannte Mosaike, also 3-zusammenhängende planare Graphen, deren Facetten Dreiecke oder Vierecke sind und auch auf verallgemeinerte Mosaike. Wir geben für jede betrachtete Klasse von Graphen Kriterien an, in wie fern für diese Klasse eine gerade Triangulierung existiert und wie diese gegebenenfalls konstruiert werden kann.