In quest of an improved algorithm for transforming plane triangulations by simultaneous flips

Abstract

In this thesis we have studied the problem of transforming one plane triangulation into another by simultaneous flips of diagonals. A triangulation is a simple planar graph consisting of only 3-cycle (triangles) faces including outerface. In a triangulation, every edge lies on two faces that form a quadrilateral. An edge flipping is an operation that replaces this edge which is a diagonal of its corresponding quadrilateral with the other diagonal of the quadrilateral. A simultaneous flip set is an edge set of a triangulation that when flipped, the resulting graph is still a triangulation. Initially, it was proved that any two triangulations of equal order (number of vertices of a graph) can be transformed from one to another using a finite sequence of edge flip operations. Later on, it was observed that to complete this transformation, O(n log n) individual flips are enough. In the continuation of the research, an algorithm was established which states that the transformation can be done in 327.1 log(n) simultaneous flips. Lately, two algorithms were introduced to improve the leading coefficient of this bound for transforming any plane triangulation into another. These two algorithms lower this bound down to 85.8 log(n) and 45.6 log(n) respectively. In this thesis, we have developed an algorithm to introduce two dominant vertices simultaneously. Using our algorithm, any pair of vertices of the triangulation can be made dominant. The process requires at most 60.8 log(n) simultaneous flips.