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 language | English |
---|---|
Pages (from-to) | 42-64 |
Number of pages | 23 |
Journal | Journal of Graph Theory |
Volume | 38 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1 Jan 2001 |
Externally published | Yes |
Keywords
- Minimal
- Minor
- Planar