Geometric and Combinatorial Structures on Graphs

In dieser Arbeit beschäftigen wir uns mit vier verschiedenen Themen: Zusammenhänge zwischen Schnyder-Wäldern und orthogonalen Flächen, die Anzahl planarer Orientierungen mit vorgegeben Ausgraden, aufspannende Bäume mit vielen Blättern und kleine ganzzahlige Realisierungen von Stapelpolytopen. Das erste Kapitel fasst bekannte Resultate zusammen, die in der Arbeit verwendet werden, und ergänzt sie mit einigen neuen Erkenntnissen. Im zweiten Kapitel beschäftigen wir uns mit Schnyder Wäldern und orthogonalen Flächen. Wir nutzen zunächst einen neuen und intuitiven Ansatz, um zu zeigen, dass es zu jedem Schnyder-Wald eine starre orthogonale Fläche gibt, in die er geodätisch eingebettet werden kann. Mit Hilfe unseres intuitiven Beweises dieses Resultates von Felsner (2001) erhalten wir einen einfachen Algorithmus zu Konstruktion eines Brightwell-Trotter Zertifikats (Brightwell und Trotter, 1997). Die anderen Ergebnisse des Kapitels beschäftigen sich mit der effizienten Darstellung orthogonaler Flächen mit Hilfe eines Schnyder Waldes und eines Vektors von Flächengewichten beziehungsweise Höhenwerten. Gegenstand des dritten Kapitels ist das Zählen planarer Orientierungen mit vorgegeben Ausgraden, die auch alpha-Orientierungen genannt werden (Felsner 2004). Sehr viele Strukturen auf planaren Graphen lassen sich mit Hilfe von alpha-Orientierungen beschreiben, dazu gehören: spannende Bäume, Eulersche Orientierungen, Schnyder Wälder und bipolare Orientierungen. Wir nutzen diese Beschreibungen um die maximale Anzahl solcher Strukturen auf planaren Graphen abzuschätzen. Wir geben unter anderem Beispiele von Triangulierungen mit 2.37^n Schnyder-Wäldern, 3-zusammenhängenden Graphen mit 3.209^n Schnyder-Wäldern und Triangulierungen mit 2.91^n bipolaren Orientierungen. Diesen unteren Schranken stehen obere Schranken von 3.56^n, 8^n und 3.97^n gegenüber. Wir präsentieren auch Ergebnisse zu Komplexität und Approximation des Zählens von alpha-Orientierungen. Spannende Bäume mit vielen Blättern sind das Thema des vierten Kapitels. Das Problem einen spannenden Baum mit größtmöglicher Anzahl von Blättern zu konstruieren ist NP-schwer. Wir zeigen für bestimmte Graphenklassen, dass alle Graphen mit n Knoten spannende Bäume mit mindestens n/a+c Blättern haben. Weiterhin konstruieren wir Beispiele aus den jeweiligen Klassen, die keinen spannenden Baum mit mehr als n/a+c Blättern haben. Unser Hauptergebnis ist eine Schranke von n/3+4/3 für eine sehr große Graphenklasse, die ein Ergebnis aus Griggs et al. (1989) verallgemeinert. Unsere Verbesserung wird möglich durch die Identifikation einer neuen Obstruktion für die Existenz von Bäumen mit n/3+c Blättern. Im fünften Kapitel beschreiben wir wie so genannte lineare und balancierte Stapelpolytope im 3-dimensionalen Raum mit polynomiellen ganzzahligen Eckenkoordinaten realisiert werden können. Außerdem folgt aus unseren Ergebnissen, dass alle Stapelpolytope mit n Ecken ganzzahlige Realisierungen der Größe 15^n haben. Wir schließen mit einer Auswahl von offenen Problemen aus den einzelnen Kapiteln.

Author dc:creator

• Zickfeld, Florian

Advisor dc:contributor.advisor

• Felsner, Stefan

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en, English

Identifier URI

urn:nbn:de:kobv:83-opus-17392
http://dx.doi.org/10.14279/depositonce-1750

OAI identifier oai:identifier

oai:depositonce.tu-berlin.de:11303/2047