Obstruction Sets for Outer-Projective-Planar Graphs.
Dan Archdeacon, Nora Hartsfield, Charles H. C. Little, Bojan Mohar · 1998
. A graph G is outer-projective-planar if it can be embedded in the projective plane so that every vertex appears on the boundary of a single face. We exhibit obstruction sets for outer-projectiveplanar graphs with respect to the subdivision, minor, and Y \\Delta orderings. Equivalently, we find the minimal non-outer-projective-planar graphs under these orderings. x1 Introduction The most frequently cited [B] result in graph theory is Kuratowski's Theorem [K], which states that a graph is planar if and only if it does not contain a subdivision of either K 5 or K 3;3 . This is an example of an obstruction theorem; a characterization of graphs with a particular property in terms of excluded subgraphs. Obstruction theorems may involve other properties besides planarity and other orderings besides the subgraph order. Let P be a property of graphs, formally, P is some collection of graphs. Let be a partial ordering on all graphs. We say that P is hereditary under if G 2 P and H G im...