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
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