Christoph Peters:
Algorithmen für gerade Triangulierungen spezieller planarer Graphen
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.