✦ LIBER ✦

Simultaneous diagonal flips in plane triangulations

✍ Scribed by Prosenjit Bose; Jurek Czyzowicz; Zhicheng Gao; Pat Morin; David R. Wood

Publisher: John Wiley and Sons
Year: 2007
Tongue: English
Weight: 468 KB
Volume: 54
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20214

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Simultaneous diagonal flips in plane triangulations are investigated. It is proved that every triangulation with n ≥ 6 vertices has a simultaneous flip into a 4‐connected triangulation, and that the set of edges to be flipped can be computed in $\cal O$(n) 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 $\cal O$(log__n__) simultaneous flips to transform one into the other. Moreover, Ω(log n) simultaneous flips are needed for some pairs of triangulations. The total number of edges flipped in this sequence is $\cal 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}\over{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}\over{7}}({n}-{2})$ edges. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 307–330, 2007

📜 SIMILAR VOLUMES

Diagonal 11-coloring of plane triangulat

Diagonal 11-coloring of plane triangulations

✍ Oleg V. Borodin 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB

## Abstract The vertices of each plane triangulation without loops and multiple edges may be colored with 11 colors so that for every two adjacent triangles [__xyz__] and [__wxy__], the vertices __x__,__y__,__w__,__z__ are colored pairwise differently.

On Diagonally 10-Coloring Plane Triangul

On Diagonally 10-Coloring Plane Triangulations

✍ Daniel P. Sanders; Yue Zhao 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 440 KB

## Abstract This article shows that the vertices of a plane triangulation may be colored with 10 colors such that every pair of vertices has different colors if they are either adjacent or diagonal, that is, that they are not adjacent but are adjacent to two faces which share an edge. This improves

Enumeration of Rooted Planar Triangulati

Enumeration of Rooted Planar Triangulations with Respect to Diagonal Flips

✍ Zhicheng Gao; Jianyu Wang 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 288 KB

We use the generating function approach to enumerate two families of rooted planar near-triangulations (2-connected, and 2-connected with no multiple edges) with respect to the number of flippable edges. It is shown that their generating functions are algebraic. Simple explicit expressions are obtai

Diagonal Flips of Triangulations on Clos

Diagonal Flips of Triangulations on Closed Surfaces Preserving Specified Properties

✍ Richard Brunet; Atsuhiro Nakamoto; Seiya Negami 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 445 KB

Consider a class P of triangulations on a closed surface F 2 , closed under vertex splitting. We shall show that any two triangulations with the same and sufficiently large number of vertices which belong to P can be transformed into each other, up to homeomorphism, by a finite sequence of diagonal

Diagonal Flips in Triangulations on Clos

Diagonal Flips in Triangulations on Closed Surfaces with Minimum Degree at Least 4

✍ Hideo Komuro; Atsuhiro Nakamoto; Seiya Negami 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 365 KB

It will be shown that any two triangulations on a closed surface, except the sphere, with minimum degree at least 4 can be transformed into each other by a finite sequence of diagonal flips through those triangulations if they have a sufficiently large and same number of vertices. The same fact hold

N-flips in even triangulations on the sp

N-flips in even triangulations on the sphere

✍ Atsuhiro Nakamoto; Tadashi Sakuma; Yusuke Suzuki 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB 👁 1 views

A triangulation is said to be even if each vertex has even degree. For even triangulations, define the N-flip and the P 2 -flip as two deformations preserving the number of vertices. We shall prove that any two even triangulations on the sphere with the same number of vertices can be transformed int