LOCAL MAXIMA IN GRADED GRAPHS OF EMBEDDINGS

Publisher Website
Google Scholar
Abstract
Summary: This paper describes four natural ways in which the set of all orientable embeddings of a graph might be regarded as the vertices of a “graded graph.” A local maximum in any of these kinds of graded graphs is an embedding such that every “adjacent” embedding has fewer faces, and consequently, higher genus. Examples are presented to show that local maxima can arise in each of the four kinds of graded graphs, thereby undermining the hope for an obvious hill‐climbing algorithm. (Some hope for a more subtle hill‐climbing algorithm may survive.)

This publication has 2 references indexed in Scilit: