Linear number of diagonal flips in triangulations on surfaces

A diagonal flip in a triangulation G on a surface is a transformation of G to replace a diagonal e in the quadrilateral region formed by two faces sharing e with another diagonal. If this operation breaks the simpleness of graphs, then we do not apply it. We shall prove that for any surface F2, ther...

Full description

Saved in:
Bibliographic Details
Published in:Electronic notes in discrete mathematics 2011-12, Vol.38, p.669-674
Main Authors: Mori, Ryuichi, Nakamoto, Atsuhiro
Format: Article
Language:English
Subjects:
bouquet
Diagonal flip
surface
triangulation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A diagonal flip in a triangulation G on a surface is a transformation of G to replace a diagonal e in the quadrilateral region formed by two faces sharing e with another diagonal. If this operation breaks the simpleness of graphs, then we do not apply it. We shall prove that for any surface F2, there exists a natural number N(F2) such that if n⩾N(F2), then any two n-vertex triangulations on F2 can be transformed into each other by O(n) diagonal flips, up to homeomorphism.
ISSN:1571-0653
1571-0653
DOI:10.1016/j.endm.2011.10.012