Diagonal flips in plane graphs with triangular and quadrangular faces

Atsuhiro Nakamoto
Yokohama National University

Naoki Matsumoto
Seikei University

PDF

Minisymposium: GRAPH IMBEDDINGS AND MAP SYMMETRIES

Content: Wagner proved that any two plane {\em triangulations} with $n > 3$ vertices can be transformed into each other by diagonal flips. His proof gives us an algorithm to transform them by $O(n^2)$ diagonal flips. However, Komuro has given an algorithm with $O(n)$ diagonal flips, and proved that the order is best possible. For plane {\em quadrangulations} with $n > 3$ vertices, there is a similar research using a kind of diagonal flips, and an $O(n)$ algorithm is also known for this class. In our talk, we focus on a plane {\em mosaic}, that is, a simple plane graph each of whose faces is triangular or quadrangular. We prove that any two mosaics with $n$ vertices can be transformed into each other by $O(n)$ diagonal flips if they have the same number of triangular faces. This improves the estimation for the number of diagonal flips given by Aichholzer et al.

Back to all abstracts