A Nebeský-Type Characterization for Relative Maximum Genus

Dan Archdeacon, C. Paul Bonnington, Jozef Širáň

Research output: Contribution to journalArticleResearchpeer-review

4 Citations (Scopus)


This paper concerns the maximum genus orientable surface upon which a given graph cellularly embeds. Classical theorems of Xuong and Nebeský give exact values for the maximum genus. The former is suited to constructing embeddings while the latter is suited to forbidding embeddings of larger genus. However, using either theorem alone requires an exhaustive search to establish the exact value. Herein we examine relative embeddings of graphs, where certain facial cycles and their orientations have been prescribed. The relative graph analogue of Xuong's theorem is known. In this paper we establish the relative graph analogue of Nebeský's theorem.

Original languageEnglish
Pages (from-to)77-98
Number of pages22
JournalJournal of Combinatorial Theory, Series B
Issue number1
Publication statusPublished - 1 May 1998
Externally publishedYes

Cite this