Obstructions for two-vertex alternating embeddings of graphs in surfaces. (January 2017)

• Record Type: Journal Article
• Authors: Mohar, Bojan; Škoda, Petr
• Is Part Of: European journal of combinatorics. Volume 59(2017)
• Page Start: 96
• Page End: 113
• Publication Date: 2017-01
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2016.08.001
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: A class of graphs that lies strictly between the classes of graphs of genus (at most) k − 1 and k is studied. For a fixed orientable surface S k of genus k, let A x y k be the minor-closed class of graphs with terminals x and y that either embed into S k − 1 or admit an embedding Π into S k such that there is a Π -face where x and y appear twice in the alternating order. In this paper, the obstructions for the classes A x y k are studied. In particular, the complete list of obstructions for A x y 1 is presented.