Simultaneous diagonal flips in plane triangulations

ABSTRACT

Simultaneous diagonal flips in plane triangulations are investigated. It is proved that every triangulation with at least six vertices has a simultaneous flip into a 4-connected triangulation, and that it can be computed in linear time. It follows that every triangulation has a simultaneous flip into a Hamiltonian triangulation. This result is used to prove that for any two n-vertex triangulations, there exists a sequence of O(log n) simultaneous flips to transform one into the other. The total number of edges flipped in this sequence is O(n). The maximum size of a simultaneous flip is then studied. It is proved that every triangulation has a simultaneous flip of at least 1/3(n − 2) edges. On the other hand, every simultaneous flip has at most n − 2 edges, and there exist triangulations with a maximum simultaneous flip of 6/7 (n − 2) edges.

REFERENCES

• 1: Therese C. Biedl , Prosenjit Bose , Erik D. Demaine , Anna Lubiw, Efficient algorithms for Petersen's matching theorem, Journal of Algorithms, v.38 n.1, p.110-134, Jan. 2001 [doi>10.1006/jagm.2000.1132]
• 2: Prosenjit Bose, Jurek Czyzowicz, Zhicheng Gao, Pat Morin, and David R. Wood. Simultaneous diagonal flips in plane triangulations. 2005. http://arxiv.org/math/0509478.
• 3: Prosenjit Bose, Vida Dujmović, and David R. Wood. Induced subgraphs of bounded treewidth and bounded degree. In Proc. 31st Workshop on Graph Theoretic Concepts in Computer Science (WG '05), vol. 3787 of Lecture Notes in Comput. Sci., pp. 175--186. Springer, 2005. http://arXiv.org/math/0505415.
• 4: Richard Brunet , Atsuhiro Nakamoto , Seiya Negami, Diagonal flips of triangulations on closed surfaces preserving specified properties, Journal of Combinatorial Theory Series B, v.68 n.2, p.295-309, Nov. 1996 [doi>10.1006/jctb.1996.0070]
• 5: N. Chiba , T. Nishizeki, The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs, Journal of Algorithms, v.10 n.2, p.187-211, June 1989 [doi>10.1016/0196-6774(89)90012-6]
• 6: Carmen Cortés, Clara Grima, Alberto Marquez, and Atsuhiro Nakamoto. Diagonal flips in outer-triangulations on closed surfaces. Discrete Math., 254(1-3):63--74, 2002.
• 7: Carmen Cortés , Atushiro Nakamoto, Diagonal flips in outer-torus triangulations, Discrete Mathematics, v.216 n.1-3, p.71-83, April 6, 2000 [doi>10.1016/S0012-365X(99)00239-3]
• 8: Hubert De Fraysseix, János Pach, and Richard Pollack. How to draw a planar graph on a grid. Combinatorica, 10(1):41--51, 1990.
• 9: Jerôme Galtier, Ferran Hurtado, Marc Noy, Stephane Pérennes, and Jorge Urrutia. Simultaneous edge flipping in triangulations. Internat. J. Comput. Geom. Appl., 13(2):113--133, 2003.
• 10: Zhicheng Gao, Jorge Urrutia, and Jianyu Wang. Diagonal flips in labelled planar triangulations. Graphs Combin., 17(4):647--657, 2001.
• 11: Zhicheng Gao , Jianyu Wang, Enumeration of rooted planar triangulations with respect to diagonal flips, Journal of Combinatorial Theory Series A, v.88 n.2, p.276-296, Nov. 1999 [doi>10.1006/jcta.1999.2996]
• 12: F. Hurtado , M. Noy, Graph of triangulations of a convex polygon and tree of triangulations, Computational Geometry: Theory and Applications, v.13 n.3, p.179-188, Sept. 1999 [doi>10.1016/S0925-7721(99)00016-4]
• 13: Ferran Hurtado, Marc Noy, and Jorge Urrutia. Flipping edges in triangulations. Discrete Comput. Geom., 22(3):333--346, 1999.
• 14: Hideo Komuro. The diagonal flips of triangulations on the sphere. Yokohama Math. J., 44(2):115--122, 1997.
• 15: Hideo Komuro and Kiyoshi Ando. Diagonal flips of pseudo triangulations on the sphere. Ars Combin., 59:225--239, 2001.
• 16: Hideo Komuro , Atsuhiro Nakamoto , Seiya Negami, Diagonal flips in triangulations on closed surfaces with minimum degree at least 4, Journal of Combinatorial Theory Series B, v.76 n.1, p.68-92, May 1999 [doi>10.1006/jctb.1998.1889]
• 17: Ryuichi Mori, Atsuhiro Nakamoto, and Katsuhiro Ota. Diagonal flips in Hamiltonian triangulations on the sphere. Graphs Combin., 19(3):413--418, 2003.
• 18: Tomoki Nakamigawa, A generalization of diagonal flips in a convex polygon, Theoretical Computer Science, v.235 n.2, p.271-282, March 28, 2000 [doi>10.1016/S0304-3975(99)00199-1]
• 19: Atsuhiro Nakamoto and Seiya Negami. Diagonal flips in graphs on closed surfaces with specified face size distributions. Yokohama Math. J., 49(2):171--180, 2002.
• 20: Seiya Negami, Diagonal flips in triangulations of surfaces, Discrete Mathematics, v.135 n.1-3, p.225-232, Dec. 25, 1994 [doi>10.1016/0012-365X(93)E0101-9]
• 21: Seiya Negami. Diagonal flips in triangulations on closed surfaces, estimating upper bounds. Yokohama Math. J., 45(2):113--124, 1998.
• 22: Seiya Negami. Diagonal flips of triangulations on surfaces, a survey. Yokohama Math. J., 47:1--40, 1999.
• 23: Seiya Negami and Atsuhiro Nakamoto. Diagonal transformations of graphs on closed surfaces. Sci. Rep. Yokohama Nat. Univ. Sect. I Math. Phys. Chem., (40):71--97, 1993.
• 24: Jean Pallo. An efficient upper bound of the rotation distance of binary trees. Inform. Process. Lett., 73(3--4):87--92, 2000.
• 25: Neil Robertson , Daniel Sanders , Paul Seymour , Robin Thomas, The four-colour theorem, Journal of Combinatorial Theory Series B, v.70 n.1, p.2-44, May 1997 [doi>10.1006/jctb.1997.1750]
• 26: Klaus Wagner. Bemerkung zum Vierfarbenproblem. Jber. Deutsch. Math. - Verein., 46:26--32, 1936.
• 27: Takahiro Watanabe and Seiya Negami. Diagonal flips in pseudo-triangulations on closed surfaces without loops. Yokohama Math. J., 47:213--223, 1999.
• 28: Hassler Whitney. A theorem on graphs. Ann. of Math. (2), 32(2):378--390, 1931.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures; Geometrical problems and computations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory