Diagonal Transformations of Graphs on Closed Surfaces
Seiya Negami, Atsuhiro Nakamoto · Institutional Repositories DataBase (IRDB) · 1993
Diagonal Transformations of Graphs on Closed Surfaces 73 triangular faces.However, if there is an edge bd in G, the diagonal flip at ac yields multiple edges between b and d, and hence G' is not a triangulation.We forbit such a diagoanl flip not to break the simpleness of graphs.The question is whether or not any two triangulations on a closed surface can be transformed into each other by diagonal flips.They are said to be equivalent under diagonal flips if they can.Of cource, they must have the same number of vertices and of edges if they are equivalent to each other.Note that triangulations with the same number of vertices have the same number of edges by Euler's formula.The following theorem is the origin of this topic and was proved by Wagner in his paper [16] written in German.An article introducing this theorem can be found in Ore's book [11] on Four Color Problem.His proof is very easy and constructive as shown below, (The meanings of "up to ambient isotopy" and "up to homeomorphism" will be explained later in the next setction.)THEOREM1 (Wagner, 1936).Any two triangulations on the sphere with the same number of vertices a7? equivalent to each other under diagonal flips, mp to ambient isotQPy.17oof Let G be any triangulation of the sphere.We represent it as a plane graph, so that there is a big triangle uovw of G and the triangular region with boundary uovw contains the whole of G. Let v, oq y; z,..., zu be the neighbors of uo, lying clockwise in this order.First suppose that uo has degree at least 4. (If deguo==4, then g=w.)If y is not adjacent to v, then we replace uox with yv to decrease the degree of uo.Otherwise, the edge yv is placed outside the rectangle uovxzy and the cycle uotuy separates x and z.Thus, x is not adjacent to g and hence uoy can be replaced with xe by a diagonal flip.Repeating these deformations, we can reduce the degree of uo to 3. Now suppose that uo has precisely three neighbors v, ui, w and consider the subgraph Gi of G bounded by the triangle uivw.By the same arguments, we can deform Gi by diagonal flips inside uivw so that ui has degree 3 in Gi and hence degree 4 in G afterward.Repeating these arguments with subgraphs Gi, G2,･･･, we get finally the triangulation which consists of the triangle uovw and the path uiu2･･･u. of vertices of degree 4 adjacent to both v and w.This is the standard form of the spherical triangulations, as shown in Figure 2. Therefore, any two triangulations of the sphere with the same number of vertices can be transformed into each other by diagonal flips via this standard form.-