Obstructions for Embedding Cubic Graphs on the Spindle Surface

Dan Archdeacon and C. Paul Bonnington

Abstract

The {em spindle surface} $S$ is the pinched surface
formed by identifying two points on the sphere. In this paper we examine
cubic graphs that minimally do not embed on the spindle surface. We give
the complete list of 21 cubic graphs that form the topological obstruction
set in the cubic order for graphs that embed on $S$.

A graph $G$ is {em nearly-planar} if there exists an edge $e$ such that
$G - e $ is planar. All planar graphs are nearly-planar. A cubic
obstruction for near-planarity is the same as an obstruction for embedding
on the spindle surface. Hence we also give the topological obstruction
set for cubic nearly-planar graphs.


Keywords
Spindle surface, graph minors, graph embeddings

Math Review Classification
Primary 05C10

Last Updated

Length
22 pages

Availability
This article is available in: