Obstruction sets for outer-cylindrical graphs

Dan Archdeacon, C. Paul Bonnington, Nathaniel Dean, Nora Hartsfield, Katherine Scott

Research output: Contribution to journalArticleResearchpeer-review

7 Citations (Scopus)

Abstract

A graph is outer-cylindrical if it embeds in the sphere so that there are two distinct faces whose boundaries together contain all the vertices. The class of outer-cylindrical graphs is closed under minors. We give the complete set of 38 minor-minimal non-outer-cylindrical graphs, or equivalently, an excluded minor characterization of outer-cylindrical graphs. We also give the obstruction sets under the related topological ordering and VΔ-Ordering.

Original languageEnglish
Pages (from-to)42-64
Number of pages23
JournalJournal of Graph Theory
Volume38
Issue number1
DOIs
Publication statusPublished - 1 Jan 2001
Externally publishedYes

Keywords

  • Minimal
  • Minor
  • Planar

Cite this