Obstructions for two-vertex alternating embeddings of graphs in surfaces

详细信息    查看全文

• 作者：Bojan Mohar¹ ; Petr &Scaron ; koda ^{pskoda@sfu.ca" class="auth_mail" title="E-mail the corresponding author}
• 刊名：European Journal of Combinatorics
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：59
• 期：Complete
• 页码：96-113
• 全文大小：532 K

文摘

A class of graphs that lies strictly between the classes of graphs of genus (at most) k−1$k-1$ and k$k$ is studied. For a fixed orientable surface S_k${\mathbb{S}}_k$ of genus k$k$, let ${\mathcal{A}}_{xy}^k$ be the minor-closed class of graphs with terminals c07d1a36c80750fe4c4c2d983e3d87" title="Click to view the MathML source">x$x$ and 20c43011bd1b2ca6791a0ccac5f" title="Click to view the MathML source">y$y$ that either embed into S_k−1${\mathbb{S}}_{k-1}$ or admit an embedding Π$\Pi$ into S_k${\mathbb{S}}_k$ such that there is a Π$\Pi$-face where c07d1a36c80750fe4c4c2d983e3d87" title="Click to view the MathML source">x$x$ and 20c43011bd1b2ca6791a0ccac5f" title="Click to view the MathML source">y$y$ appear twice in the alternating order. In this paper, the obstructions for the classes ${\mathcal{A}}_{xy}^k$ are studied. In particular, the complete list of obstructions for ${\mathcal{A}}_{xy}^1$ is presented.