Geometric and Combinatorial Structures on Graphs
| dc.contributor.advisor | Felsner, Stefan | en |
| dc.contributor.author | Zickfeld, Florian | en |
| dc.contributor.grantor | Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften | en |
| dc.date.accepted | 2007-12-20 | |
| dc.date.accessioned | 2015-11-20T17:48:32Z | |
| dc.date.available | 2008-01-09T12:00:00Z | |
| dc.date.issued | 2008-01-09 | |
| dc.date.submitted | 2008-01-09 | |
| dc.description.abstract | 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. | de |
| dc.description.abstract | The thesis is concerned with four main topics: connection of Schnyder woods and orthogonal surfaces, the number of planar orientations with prescribed out-degrees, spanning trees with many leaves, and small integer realizations of stacked polytopes. The first chapter gives an overview of known results that we use in the thesis and complements them with a few new facts. In the second chapter we study connections between Schnyder woods and orthogonal surfaces. Schnyder woods and the face counting approach have important applications in graph drawing and dimension theory. Orthogonal surfaces explain the connections between these seemingly unrelated notions. We use these connections for an intuitive proof of the Brightwell-Trotter Theorem which says that the face lattice of a 3-polytope minus one face has dimension three. Our proof yields a companion linear time algorithm for the construction of the three linear orders that realize the face lattice. Coplanar orthogonal surfaces are in correspondence with a large class of convex straight line drawings of 3-connected planar graphs. We show that Schnyder's face counting approach with weighted faces can be used to construct all coplanar orthogonal surfaces and hence the corresponding drawings. Appropriate weights are computable in linear time. In the third chapter we deal with the asymptotic enumeration of combinatorial structures on planar maps. Prominent instances of such problems are the enumeration of spanning trees, bipartite perfect matchings and ice models. The notion of planar orientations with prescribed out-degrees (short: alpha-orientations) unifies many different combinatorial structures, including the afore mentioned. We ask for the number of alpha-orientations and also for special instances thereof, such as Schnyder woods and bipolar orientations. The main focus of this paper are bounds for the maximum number of such structures that a planar map with n vertices can have. We give examples of triangulations with 2.37^n Schnyder woods, 3-connected planar maps with 3.209^n Schnyder woods and inner triangulations with 2.91^n bipolar orientations. These lower bounds are accompanied by upper bounds of 3.56^n, 8^n and 3.97^n respectively. We also show that for any planar map M and any alpha the number of alpha-orientations is bounded from above by 3.73^n and present a family of maps which have at least 2.598^n alpha-orientations for n big enough. In the fourth chapter we deal with spanning trees with many leaves. We show that every graph with minimum degree 3 and certain excluded subgraphs has a spanning tree with at least (n+4)/3 leaves. It is known that graphs with minimum degree 3 have spanning trees with n/4+2 leaves and that this can be improved to (n+4)/3 for cubic graphs without the diamond K_4-e as a subgraph. Both bounds are best possible. We present an example showing that for graphs with minimum degree 3 not only diamond necklaces (concatenations of diamonds) are an obstruction for obtaining a bound of the form n/3+c. Namely we use the so-called blossom graph to build a graph family without diamond necklaces such that every spanning tree has at most 4n/13+2 leaves. We then show that the bound (n+4)/3 can indeed be achieved when diamond necklaces and blossoms are excluded as subgraphs. This bound is also best possible. The fifth chapter of the thesis deals with small integer realizations of stacked polytopes. We present realizations of 3-dimensional stacked polytopes with integral vertex coordinates. The best known upper bounds for the vertex coordinates are exponential in the number of vertices, the best lower bound is polynomial. While one approach to this problem is to improve the base of the exponential upper bound, we focus on giving polynomial upper bounds for special classes of polytopes. We give such polynomial bounds for linear and balanced stacked polytopes and also improve the upper bound to 15^n for the class of all stacked polytopes with n vertices. We conclude with some open problems. | en |
| dc.identifier.uri | urn:nbn:de:kobv:83-opus-17392 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/2047 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-1750 | |
| dc.language | English | en |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | Asymptotisches Zählen von Orientierungen | de |
| dc.subject.other | Aufspannende Bäume | de |
| dc.subject.other | Dimension von Graphen | de |
| dc.subject.other | Graphenzeichnen | de |
| dc.subject.other | Realisierungen von 3-Polytopen | de |
| dc.subject.other | Asymptotic Counting of Orientations | en |
| dc.subject.other | Graph Dimension | en |
| dc.subject.other | Graph Drawing | en |
| dc.subject.other | Realizations of 3-Polytopes | en |
| dc.subject.other | Spanning Trees | en |
| dc.title | Geometric and Combinatorial Structures on Graphs | en |
| dc.title.translated | Geometrische und Kombinatorische Strukturen auf Graphen | de |
| dc.type | Doctoral Thesis | en |
| dc.type.version | publishedVersion | en |
| tub.accessrights.dnb | free | * |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.identifier.opus3 | 1739 | |
| tub.identifier.opus4 | 1658 | |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
Files
Original bundle
1 - 1 of 1