Diagonal flips in pseudo-triangulations on closed surfaces (Q5948976)

From MaRDI portal
scientific article; zbMATH DE number 1672501
Language Label Description Also known as
English
Diagonal flips in pseudo-triangulations on closed surfaces
scientific article; zbMATH DE number 1672501

    Statements

    Diagonal flips in pseudo-triangulations on closed surfaces (English)
    0 references
    0 references
    22 July 2002
    0 references
    The author has previously established [Discrete Math. 135, No. 1-3, 225-232 (1994; Zbl 0823.05028)] that, for each closed surface \(F^2\), there is a natural number \(N(F^2)\) so that two triangulations on \(F^2\), both of graphs (having neither loops nor multiple edges) of order \(n\), can be transformed into each other by a sequence of diagonal flips, if \(n\geq N(F^2)\). (Each diagonal flip replaces two triangles \(abc\) and \(acd\) with the triangles \(abd\) and \(bcd.)\) In the present paper he investigates the pseudograph case (loops and multiple edges allowed), estimating the length of a sequence of diagonal flips. The arguments are then applied to graph triangulations, to obtain a linear upper bound for \(N(F^2)\) in terms of the genus of \(F^2\).
    0 references
    triangulations
    0 references
    diagonal flips
    0 references
    genus
    0 references

    Identifiers