Degree-Constrained Pseudo-Triangulations
TU Graz, Universidad de Alcalà, Freie Universität Berlin
01.03.2011 - 01.03.2014
computational geometry, geometric graph, triangulation, pseudo-triangulation, vertex degree, face degree

The project is in the area of computational and combinatorial geometry, a part of theoretical computer science. We focus on geometric (i.e., straight-line) graphs, more specifically triangulations and pseudo-triangulations of point sets in the plane. Pseudo-triangulations are a generalization of triangulations that have applications in, e.g., motion planning and rigidity theory. We will investigate combinatorial properties of these meshes in relation with both their vertex and face degrees. We will work on triangulations with constraints on the parity of vertex degrees. The general problem asks, for a given point set with parity assignments, for how many points the parity requirement can be fulfilled in the best triangulation. While this number can be linear in the size of the point set, the problem is still open for the cases where all vertices should have the same parity. Triangulations with many odd-degree vertices can be used to solve a bi-chromatic variant of a problem stated by Erdös and Szekeres, while triangulations with all inner vertices even are properly vertex 3-colorable and therefore are of interest in the field of guarding and illumination. While there exists an algorithm for constructing pseudo-triangulations that adhere to all but at most 3 parity constraints, the problem is open for pseudo-triangulations with face degrees limited by a constant. However, the latter are of special interest as the bound does not increase the size of the graph, but the mesh can be transformed locally by constant-time operations (i.e., edge flips). We will investigate properties of restricted pseudo-triangulations. We will address the question whether any (pseudo-)triangulation of a given point set can be transformed by flips into any other. While this is known to be true in general, there are many open variations of the problem when vertex or face degrees are bounded. Further, the complexity of computing the exact number of flips needed for such a transformation is still open.