Search

This dissertation studies two natural Markov chains, each living on a family of finite distributive lattices and some related results on the enumeration of lattice paths. In the first part of this body of work, we introduce a coupling method – the block coupling technique – and apply it to the k-heights of some families of plane graphs. This gives some insight into the behaviour of the up/down Markov chain on these distributive lattices. Espe- cially it yields some upper bounds to the mixing time of the face flip Markov chain for the sets of 2-heights on some families of graphs, which is bounded by a polynomial in the number of vertices of the graph (and therefor polynomial logarithmic in the size of the state space / set of 2-heights). The second part is accepted for publication by the Journal of Integer Sequences. It focuses on the enumeration of bounded lattice paths and uses transfer matrices and methods from linear algebra to do so. Using these techniques we were able to enumerate a rather general class of lattice paths, which reduce to a lot of different well known integer sequences as special cases, and therefore group them together. Also this method looks promising to enumerate other families of sequences, as it links various fields (Graph Theory, Linear Algebra, and Lattice Path Enumeration) in an easily applicable way. Finally, the third part, considers the distributive lattices of α-orientations on planar graphs and the face flip Markov chain on these sets. It uses tower moves, another coupling method, to show that the the up/down Markov chain is rapid mixing on the set of 2-orientations of planar quadrangulations of maximum degree 4. In addition, this part contains results using the congestion of some carefully chosen families of graphs to prove, that for graphs containing vertices with high degree the Markov chain is not rapid mixing, i.e. that the mixing time can not be bound from above by some polynomial in the logarithm of the size of the state space. Diese Dissertation untersucht zwei natürliche Markov Ketten, die jeweils auf einer Familie endlicher distributiver Verbände leben. Weiterhin enthält sie einige Verwandte Resultate über das Zählen von Gitter-Pfaden. Im ersten Teil der Arbeit stellen wir die Block Coupling Methode vor und wenden sie auf k-heights einiger Familien planarer Graphen an. Dieses gibt etwas Einblick in das Verhalten der up/down-Markov Kette auf diesen distributiven Verbänden. Insbesondere liefern die Untersuchungen einige obere Schranken für die Mischzeit der FaceFlip Markov Kette auf der Menge der 2-heights einiger Graphen-Familien. Wir zeigen dass diese beschränkt ist durch ein Polynom in den Anzahl der Knoten der Graphen (was implizit bedeutet, dass sie polynomiel logarithmisch ist in der Anzahl der 2-heights). Der zweite Teil der Arbeit beschäftigt sich mit dem Zählen beschränkter Gitter-Pfade. Hier werden Transfer Matrizen und Methoden der Linearen Algebra angewendet um diese Pfade zu zählen. Auf diese Art war es möglich, viele bereits bekannte Integer-Sequenzes über die untersuchten beschränkten Gitter-Pfade zu beschreiben und sie daher in einen Zusammenhang zu stellen. Insbesondere scheint diese Methode eine Möglichkeit darzustellen, weitere Familien von Folgen zu untersuchen und sie verbindet einige verschiedene Gebiete der Mathematik. Die Ergebnisse die in diesem Kapitel vorgestellt werden wurden auch vom Journal of Integer Sequences zur Publikation akzeptiert. Der dritte Teil schliesslich beschäftigt sich mit den distributiven Verbänden von Alpha-Orientierungen planarer Graphen und der Face Flip Markov Kette auf diesen. Es werden Tower Movers, eine weitere coupling Methode, genutzt um zu zeigen, dass die up/down Markov Kette für 2-Orientierungen planarer Quadrangulierungen mit maximal Grad 4 schnell mischend ist. Zusätzlich enthält dieser Teil Resultate, die mithilfe sorgfältig konstruierter Graphenfamilien zeigen, dass für Graphen mit hohem Grad nicht erwartet werden kann, dass die untersuchte Markov Kette schnell mischt.

Given a planar graph $G$ and a partition of the neighbors of each vertex $v$ in four sets $UR(v)$, $UL(v)$, $DL(v)$, and $DR(v)$, the problem Windrose Planarity asks to decide whether $G$ admits a windrose-planar drawing, that is, a planar drawing in which (i) each neighbor $u \in UR(v)$ is above and to the right of $v$, (ii) each neighbor $u \in UL(v)$ is above and to the left of $v$, (iii) each neighbor $u \in DL(v)$ is below and to the left of $v$, (iv) each neighbor $u \in DR(v)$ is below and to the right of $v$, and (v) edges are represented by curves that are monotone with respect to each axis. By exploiting both the horizontal and the vertical relationship among vertices, windrose-planar drawings allow to simultaneously visualize two partial orders defined by means of the edges of the graph. Although the problem is NP-hard in the general case, we give a polynomial-time algorithm for testing whether there exists a windrose-planar drawing that respects a given combinatorial embedding. This algorithm is based on a characterization of the plane triangulations admitting a windrose-planar drawing. Furthermore, for any embedded graph with $n$ vertices that has a windrose-planar drawing, we can construct one with at most one bend per edge and with at most $2n-5$ bends in total, which lies on the $3n \times 3n$ grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area., Appeared in Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)

In this thesis we develop and analyze algorithms for computing space-filling curve orders, Delaunay Tessellations and flow complexes of point sets. For space-filling curve orders and Delaunay Tessellations the emphasis lies on an average-case analysis of the algorithms. For flow complexes the emphasis lies on their computation in higher dimensions. In a space-filling curve order of a point set, points which are close in the order are also close in space. We discuss algorithms for computing space-filling curve orders based on radix sort. We give an average-case analysis which shows that these orders can be computed in linear expected time for many point distributions. As discrete counterparts of space-filling curves we consider grid traversals and discuss finding optimal grid traversals for different locality measures using heuristics for the quadratic assignment problem. The Delaunay Tessellation of a point set is a simplicial complex capturing proximity relations of the points. We analyze incremental constructions of Delaunay Tessellations along space-filling curve orders. First we give a generalized and refined analysis of incremental constructions con BRIO, i.e., where points are inserted in random rounds. Based on this we analyze incremental constructions along space- filling curve orders for uniformly distributed points from a bounded convex region in the plane, normally distributed points in the plane, and uniformly distributed points from a d-cube in higher dimensions. In the first case we analyze the expected structure of the Delaunay Tessellation and in the other cases the structure of the space-filling curve order. We show for these point distributions that incremental constructions con BRIO of Delaunay Tessellations run in linear expected time using space-filling curve orders. The flow complex of a point set is the collection of stable manifolds of the flow induced by the distance function of the point set. We give an algorithm for computing the flow complex in higher dimensions. The algorithm is based on the Delaunay Tessellation and Voronoi Diagram of the point set and the recursive nature of the flow. Based on this algorithm we give a topological analysis of flow shapes, i.e., the underlying spaces of subcomplexes of the flow complex. In particular we show that flow shapes are homotopy equivalent to the corresponding unions of balls., In dieser Arbeit werden Algorithmen zur Berechnung von Ordnungen entlang raumfüllender Kurven, von Delaunay-Triangulierungen und von Flusskomplexen entworfen und analysiert. Für Ordnungen entlang raumfüllender Kurven und für Delaunay-Triangulierungen liegt der Schwerpunkt auf einer Analyse der Algorithmen im durchschnittlichen Fall. Für Flusskomplexe liegt der Schwerpunkt auf deren Berechnung in höheren Dimensionen. In einer Ordnung entlang einer raumfüllenden Kurve sind Punkte, die nah in der Ordnung sind, auch nah im Raum. Wir diskutieren Algorithmen zur Berechnung solcher Ordnungen basierend auf Radixsort. Wir geben eine Analyse für den durchschnittlichen Fall, in der wir zeigen, dass diese Ordnungen für viele Punktverteilungen in linearer erwarteter Zeit berechnet werden können. Als diskrete Gegenstücke zu raumfüllenden Kurven betrachten wir Indizierungen von Gitterpunkten. Für verschiedene Lokalitätsmaße berechnen wir Indizierungen basierend auf Heuristiken für das quadratische Zuordnungsproblem. Die Delaunay- Triangulierung einer Punktmenge ist ein simplizialer Komplex auf den Punkten, welcher Nachbarschaftsbeziehungen zwischen den Punkten wiedergibt. Wir analysieren die Laufzeit von inkrementellen Konstruktionen von Delaunay- Triangulierungen, bei denen entlang raumfüllender Kurven eingefügt wird. Zunächst geben wir eine verallgemeinerte und verfeinerte Analyse von inkrementellen Konstruktionen con BRIO, also Konstruktionen, bei denen Punkte in zufälligen Runden eingefügt werden. Darauf basierend analysieren wir inkrementelle Konstruktion entlang raumfüllender Kurven für gleichmäßig verteilte Punkte aus einem beschränkten konvexen Gebiet für normalverteilte Punkte in der Ebene und für gleichmäßig verteilte Punkte aus einem d-dimensionalen Würfel in höheren Dimensionen. Im ersten Fall analysieren wir die erwartete Struktur der Delaunay-Triangulierung und in den anderen Fällen die Struktur der Ordnung entlang der raumfüllenden Kurve. Wir zeigen für diese Verteilungen, dass inkrementelle Konstruktionen con BRIO entlang raumfüllender Kurven in linearer erwarteter Zeit laufen. Der Flusskomplex einer Punktmenge ist die Gesamtheit der stabilen Mannigfaltigkeiten des Flusses, der durch die Distanzfunktion der Punktmenge induziert wird. Wir geben einen Algorithmus zur Berechnung des Flusskomplex in höheren Dimensionen an. Dieser beruht auf der Delaunay-Triangulierung, dem Voronoi Diagramm und der rekursiven Natur des Flusses. Basierend auf dem Algorithmus geben wir eine topologische Analyse der unterliegenden Räume von Subkomplexen des Flusskomplex. Wir zeigen, dass ein solcher Raum homotopieäquivalent zu der entsprechenden Vereinigung von Kugeln ist.

We show that if a planar graph $G$ has a plane straight-line drawing in which a subset $S$ of its vertices are collinear, then for any set of points, $X$, in the plane with $|X|=|S|$, there is a plane straight-line drawing of $G$ in which the vertices in $S$ are mapped to the points in $X$. This solves an open problem posed by Ravsky and Verbitsky in 2008. In their terminology, we show that every collinear set is free. This result has applications in graph drawing, including untangling, column planarity, universal point subsets, and partial simultaneous drawings., Comment: 29 pages, 12 figures