Counting Triangulations of Fixed Cardinal Degrees
By: Erin Chambers , Tim Ophelders , Anna Schenfisch and more
Potential Business Impact:
Finds many ways to connect dots on a map.
A fixed set of vertices in the plane may have multiple planar straight-line triangulations in which the degree of each vertex is the same. As such, the degree information does not completely determine the triangulation. We show that even if we know, for each vertex, the number of neighbors in each of the four cardinal directions, the triangulation is not completely determined. In fact, we show that counting such triangulations is #P-hard via a reduction from #3-regular bipartite planar vertex cover.
Similar Papers
Counting Number of Triangulations of Point Sets: Reinterpreting and Generalizing the Triangulation Polynomials
Computational Geometry
Counts ways to connect dots in shapes.
A Simplified Proof for the Edge-Density of 4-Planar Graphs
Combinatorics
Makes drawings with fewer crossings possible.
On saturated triangulation-free convex geometric graphs
Combinatorics
Finds special shapes with fewest possible lines.