Forbidding Edges Between Points in the Plane to Disconnect the Triangulation Flip Graph

EasyChair Preprint 7927

Abstract

The flip graph for a set P of points in the plane has a vertex for every triangulation of P, and an edge when two triangulations differ by one flip that replaces one triangulation edge by another. The flip graph is known to be connected even if some triangulations edge are constrained to be used. We study connectivity of the flip graph when some triangulation edges are forbidden.

A set X of edges between points of P is a flip cut set if eliminating all triangulations that contain edges of X results in a disconnected flip graph. If X is a single edge it is called a flip cut edge. The flip cut number of P is the minimum size of a flip cut set. We give an algorithm to test if an edge is a flip cut edge. For a set of n points in convex position (whose flip graph is the 1-skeleton of the associahedron) we prove that the flip cut number is n-3.

Keyphrases: algorithm, associahedra, computational geometry, connectivity, convex polygon, flip cut edge, flip cut number, flip graph, graph, reconfiguration, triangulations

@booklet{EasyChair:7927,
  author    = {Reza Bigdeli and Anna Lubiw},
  title     = {Forbidding Edges Between Points in the Plane to Disconnect the Triangulation Flip Graph},
  howpublished = {EasyChair Preprint 7927},
  year      = {EasyChair, 2022}}