Diagonal transformations of graphs and Dehn twists of surfaces (Q1362098)

The authors are interested on two simple operations in graphs, the diagonal slide and diagonal rotation. The operations replace edges shared by two adjacent quadrilateral faces on a cellular embedding of the graph in a closed surface, to produce a new embedded graph. Two graphs are equivalent if a finite sequence of these operations takes one into the other. A quadrangulation is an embedded graph whose faces are all quadrilaterals. The authors prove the following theorem: For any closed surface \(F^2\), there exists a positive integer \(M(F^2)\) such that for any pair of bipartite quadrangulations \(G_1,G_2\) with \(|V(G_1) |=|V(G_2) |\geq M(F^2)\), \(G_1\) and \(G_2\) are equivalent up to isotopy. This is a variation of other results, for the case of triangulations, due to \textit{R. Brunet}, the first author and \textit{S. Negami} [J. Comb. Theory, Ser. B 68, No. 2, 295-309, Art. No. 0070 (1996; Zbl 0861.05021)].