Local extrema in genus‐stratified graphs
Jonathan L. Gross, Robert G. Rieper · Journal of Graph Theory · 1991
Abstract Beyond the obvious organization of all the orientable imbeddings of a graph according to the genus of the imbedding surface, there are several seemingly natural ways to ascribe proximity of imbeddings. One of these is to stipulate that two imbeddings are adjacent if one imbedding can be obtained from the other by moving one end of an edge in its rotation. If one associates “altitude” with genus, then one might hope to construct algorithms for minimum genus and maximum genus by descent and ascent, respectively. This investigation of the structure of the system of orientable graph imbeddings reveals that although there may occur arbitrarily deep traps among the local minima, there cannot exist any strict local maxima. These new discoveries seem consistent with a known contrast in the computational complexity of the maximum genus and minimum genus problems. That is, whereas Furst, Gross, and McGeoch have devised a polynomial‐time algorithm to find the maximum genus of an arbitrary graph, Thomassen has proved that the problem of finding the minimum genus is NP‐complete.