A Nebeský-type characterization for relative maximum genus (Q1272649)

A relative embedding of a graph is a 2-cell embedding where certain closed walks are prescribed as face boundaries. This paper is concerned with determining the maximum relative genus of a graph with respect to a set of closed walks. In the nonrelative case, the maximum genus is usually calculated by means of two classical theorems due to, respectively, Xuong and Nebeský, which in a certain sense complement each other. While the relative analogue of Xuong's theorem is known (see \textit{C. P. Bonnington} [J. Comb. Theory, Ser. B 60, No. 2, 195-206 (1994; Zbl 0794.05016)]), the analogue of Nebeský's theorem is the main result of this paper.