Menu
The 2-cell embeddings of graphs on closed surfaces have been widely studied. It is well known that (2-cell) embedding a given graph \(G\) on a closed orientable surface is equivalent to cyclically ordering the darts incident to each vertex of \(G\). In this paper, we study the following problem: given a genus \(g\) embedding \(\in\) of the graph \(G\) and a vertex of \(G\), how many different ways of reembedding the vertex such that the resulting embedding \(\in’\) is of genus \(g + \Delta g\)? We give formulas to compute this quantity and the local minimal genus achieved by reembedding. In the process, we obtain miscellaneous results. In particular, if there exists a one-face embedding of \(G\), then the probability of a random embedding of \(G\) to be one-face is at least \(\prod_{v \in V(G)} \frac{2}{\deg(v) + 2}\) where \(\deg(v)\) denotes the vertex degree of \(v\). Furthermore, we obtain an easy-to-check necessary condition for a given embedding of \(G\) to be an embedding of minimum genus.