Premium
LOCAL MAXIMA IN GRADED GRAPHS OF EMBEDDINGS
Author(s) -
Gross Jonathan L.,
Tucker Thomas W.
Publication year - 1979
Publication title -
annals of the new york academy of sciences
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.712
H-Index - 248
eISSN - 1749-6632
pISSN - 0077-8923
DOI - 10.1111/j.1749-6632.1979.tb32797.x
Subject(s) - embedding , hill climbing , maxima , combinatorics , graph , mathematics , climbing , book embedding , set (abstract data type) , computer science , discrete mathematics , 1 planar graph , chordal graph , algorithm , artificial intelligence , geography , art , performance art , programming language , art history , archaeology
S ummary 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.)