Diagonal Flips of Pseudo Triangulations on the Sphere

A plane graph is an embedding of a planar graph into the sphere which may have multiple edges and loops. A face of a plane graph is said to be a pseudo triangle if either the boundary of it has three distinct edges or the boundary of it consists of a loop and a pendant edge. A plane pseudo triangulation is a connected plane graph of which each face is a pseudo triangle. If a plane pseudo triangulation has neither a multiple edge nor a loop, then it is a plane triangulation. As a generalization of the diagonal flip of a plane triangulation, the diagonal flip of a plane pseudo triangulation is naturally defined. In this paper we show that any two plane pseudo triangulations of order \(n\) can be transformed into each other, up to ambient isotopy, by at most \(14n – 64\) diagonal flips if \(n \geq 7\). We also show that for a positive integer \(n \geq 5\), there are two plane pseudo triangulations with \(n\) vertices such that at least \(4n – 15\) diagonal flips are needed to transform into each other.