Obstruction sets for outer-projective-planar graphs

MaRDI QIDQ2713608zbMATH OpenFDO

Authors Nora Hartsfield, C. H. C. Little, Bojan Mohar, Dan S. Archdeacon

Publication date 10 June 2001

Published in Ars Combinatoria (Search for Journal in Brave)

zbMATH Keywords

\(Y\Delta \) orderminor orderouter-projective-planar graphsubdivision order

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Review text

A graph is outer-projective-planar if it can be embedded in the projective plane so that all vertices lie on the boundary of a single face. A set of 103 subdivision-minimal non-projective-planar graphs was found by \textit{H. H. Glover, J. P. Huneke} and \textit{C. S. Wang} [J. Comb. Theory, Ser. B 27, 332-370 (1979; Zbl 0352.05027)] and its completeness was proven by \textit{D. Archdeacon} [J. Graph Theory 5, 243-246 (1981; Zbl 0464.05028)]. This paper deals with obstruction sets for outer-projective-planar graphs, with respect to subdivision ordering, minor ordering and \(Y\Delta \) ordering of graphs. The obstruction sets have 45, 32 and 9 graphs, respectively.

Recommendations

• Obstruction sets for outer-cylindrical graphs
• Internally 4-connected projective-planar graphs
• Minor-minimal non-projective planar graphs with an internal 3-separation
• Hall-type results for 3-connected projective graphs
• A generalization of outerplanar graphs

Cited in

(8)

• Non-separating planar graphs
• Four-searchable biconnected outerplanar graphs
• Variations on a theme of Kuratowski
• Obstruction sets for outer-cylindrical graphs
• Outerplanarity without accumulation in the cylinder and the Möbius band
• Forbidden minors: finding the finite few
• Survey article: consequences of some outerplanarity extensions
• Links in projective planar graphs

This page was built for publication: Obstruction sets for outer-projective-planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2713608)