Obstruction sets for outer-cylindrical graphs

DOI10.1002/JGT.1023MaRDI QIDQ2746484zbMATH OpenOpenAlexFDO

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

Publication date 9 October 2002

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/jgt.1023

zbMATH Keywords

excluded minorouter-cylindrical graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75) Graph minors (05C83)

Review text

A graph is said to be outer-cylindrical if it can be embedded in the plane in such a way that each vertex lies on the boundary of at least one of two distinguished faces. The class of outer-cylindrical graphs is closed under the taking of minors. NEWLINENEWLINENEWLINEThe authors find a complete set of minimal excluded minors for outer-cylindrical graphs, of which there are 38. They also determine the obstruction sets under other graph orderings.

Recommendations

• Obstruction sets for outer-projective-planar graphs
• scientific article; zbMATH DE number 1159454
• Outerplanarity without accumulation in the cylinder and the Möbius band
• scientific article; zbMATH DE number 2192139
• Outerplanar obstructions for a feedback vertex set

Cites work

• A kuratowski theorem for the projective plane
• Disjoint homotopic paths and trees in a planar graph
• Graph minors. XX: Wagner's conjecture
• NETPAD: An interactive graphics system for network modeling and optimization
• On obstructions to small face covers in planar graphs
• On the Complexity of Covering Vertices by Faces in a Planar Graph

Cited in

(8)

• Halin's theorem for cubic graphs on an annulus
• Non-separating planar graphs
• Four-searchable biconnected outerplanar graphs
• Variations on a theme of Kuratowski
• Obstruction sets for outer-projective-planar graphs
• Outerplanarity without accumulation in the cylinder and the Möbius band
• scientific article; zbMATH DE number 2192139 (Why is no real title available?)
• Survey article: consequences of some outerplanarity extensions

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

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