We explore the problem of transforming plane triangulations using simultaneous diagonal flips. Wagner showed that any n-vertex plane triangulation can be transformed to any other plane triangulation on equal number of vertices using a finite sequence of diagonal flips. Later on it has been established that O(n) individual flips suffice to complete this transformation. Bose et al. showed that the transformation can also be done in 4 × ( 2 / log 54/53 + 2 / log 6/5 ) logn + 2 ≈ 327.1 log n simultaneous flips. This bound is asymptotically tight. We present two algorithms to improve the leading coefficient of this bound for transforming any plane triangulation into any other. The first of the two algorithms lowers this bound down to 4 × ( 2 / log 12/11 + 2 / log 9/7 ) logn + 2 ≈ 85.8 log n. By processing and preprocessing the interior and exterior of the triangulation’s Hamiltonian cycle parallelly in an interlaced fashion, we make further improvement of the algorithm from ≈ 327.1 log n down to 12 / log 6/5 logn + 2 ≈ 45.6 log n.

本文我們探討平面圖形的嚴格d維矩形表示法。我們證明了四連通三角平面圖有嚴格的二維矩形表示法，而且我們推廣到每一個平面圖都有嚴格的三維矩形表示法。我們的目標是希望能在平面圖矩形表示法的現今地位上，提供新的洞悉,並給未來學習者一個方向。 / We study strict d-box representations of planar graphs. We prove that a 4-connected planar triangulation graph G has a strict 2-box representation. We extend this result to that every planar graph has a strict 3-box representation. Our goal is to provide some fresh insights into the current status of research in the area while suggesting directions for the future.