Obstructions for the Disk and the Cylinder Embedding Extension Problems

Summary

Let S be a closed surface with boundary ∂S and let G be a graph. Let K ⊆ G be a subgraph embedded in S such that ∂S ⊆ K. An embedding extension of K to G is an embedding of G in S that coincides on K with the given embedding of K. Minimal obstructions for the existence of embedding extensions are classified in cases when S is the disk or the cylinder. Linear time algorithms are presented that either find an embedding extension, or return an obstruction to the existence of extensions. These results are to be used as the corner stones in the design of linear time algorithms for the embeddability of graphs in an arbitrary surface and for solving more general embedding extension problems.

Introduction

Let K be a subgraph of G. A K-component or a K-bridge in G is a subgraph of G that is either an edge e ∈ E(G)\E(K) (together with its endpoints) that has both endpoints in K, or it is a connected component of G − V(K) together with all edges (and their endpoints) between this component and K. Each edge of a K-component R having an endpoint in K is a foot of R. The vertices of R ∩ K are the vertices of attachment of R. A vertex of K of degree in K different from 2 is a main vertex of K.