Search

Given a triangulation of a point set in the plane, a flip deletes an edge e whose removal leaves a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge. It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips, but we characterize when this is possible. There is an obvious necessary condition: for each label l, if edge e has label l in the first triangulation and edge f has label l in the second triangulation, then there must be some sequence of flips that moves label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot formulated the Orbit Conjecture, which states that this necessary condition is also sufficient, i.e. that all labels can be simultaneously mapped to their destination if and only if each label individually can be mapped to its destination. We prove this conjecture. Furthermore, we give a polynomial-time algorithm (with O (n 8) being a crude bound on the run-time) to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of O (n 7) on the length of the flip sequence. Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the flip complex, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture. [ABSTRACT FROM AUTHOR]

In this article, we extend the definition of Christoffel words to directed subgraphs of the hypercubic lattice in an arbitrary dimension that we call Christoffel graphs. Christoffel graphs, when $$d=2$$ , correspond to the well-known Christoffel words. Due to periodicity, the $$d$$ -dimensional Christoffel graph can be embedded in a $$(d-1)$$ -torus (a parallelogram when $$d=3$$ ). We show that Christoffel graphs have similar properties to those of Christoffel words: symmetry of their central part and conjugation with their reversal. Our main result extends Pirillo's theorem (characterization of Christoffel words which asserts that a word $$amb$$ is a Christoffel word if and only if it is conjugate to $$bma$$ ) to an arbitrary dimension. In the generalization, the map $$amb\mapsto bma$$ is seen as a flip operation on graphs embedded in $$\mathbb {Z}^d$$ and the conjugation is a translation. We show that a fully periodic subgraph of the hypercubic lattice is a translation of its flip if and only if it is a Christoffel graph. [ABSTRACT FROM AUTHOR]

We study the set of all pseudoline arrangements with contact points which cover a given support. We define a natural notion of flip between these arrangements and study the graph of these flips. In particular, we provide an enumeration algorithm for arrangements with a given support, based on the properties of certain greedy pseudoline arrangements and on their connection with sorting networks. Both the running time per arrangement and the working space of our algorithm are polynomial. As the motivation for this work, we provide in this paper a new interpretation of both pseudotriangulations and multitriangulations in terms of pseudoline arrangements on specific supports. This interpretation explains their common properties and leads to a natural definition of multipseudotriangulations, which generalizes both. We study elementary properties of multipseudotriangulations and compare them to iterations of pseudotriangulations. [ABSTRACT FROM AUTHOR]