Obstruction sets for outer‐cylindrical graphs
Dan Archdeacon, C. Paul Bonnington, Nathaniel Dean, Nora Hartsfield, Katherine Scott · Journal of Graph Theory · 2001
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 Y Δ‐ordering. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 42–64, 2001