Obstructions for two-vertex alternating embeddings of graphs in surfaces

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

P i

into

S_{k}

such that there is a

P i

-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.

Recommendations

Cites Work

This page was built for publication: Obstructions for two-vertex alternating embeddings of graphs in surfaces