A NEBESKY-TYPE CHARACTERIZATION FOR RELATIVE MAXIMUM GENUS

This paper concerns the maximum genus orientable surface upon which a given graph cellularly embeds. Classical theorems of Xuong and Nebesky give exact values for the maximum genus. The former is suited to cons tructing embeddings while the latter is suited to forbidding embedding s of larger genus. However, using either theorem alone requires an exh austive search to establish the exact value. Herein we examine relativ e embeddings of graphs, where certain Facial cycles and their orientat ions have been prescribed. Thee relative graph analogue of Xuong's the orem is known. In this paper we establish the relative graph analogue of Nebesky's theorem. (C) 1998 Academic Press.