Braced Edges in Plane Triangulations
Roger B. Eggleton, James A. MacDougall, Latif Al‐Hakim · 1990
A plane triangulation is an embedding of a maximal planar graph in the Euclidean plane. Foulds and Robinson (1979) first studied the problem of transforming one triangulation to another by a sequence of diagonal operations, where a diagonal operation deletes one edge and inserts the other diagonal of the resulting quadrilateral face. An edge which cannot be removed by a single diagonal operation is called braced. This paper is a study of the possible number and distribution of braced edges in a triangulation. It shows that at most $2n-4$ edges of a triangulation of order $n$ can be braced, and that for any $r \leq 2n-4$ (with exactly one exception) there is a plane triangulation of order $n$ with $r$ braced edges, so long as $n$ is large enough.