Obstructions of connectivity two for embedding graphs into the torus

DOI10.4153/CJM-2014-025-XMaRDI QIDQ2933708zbMATH OpenOpenAlexFDO

Authors Bojan Mohar, Petr Škoda

Publication date 5 December 2014

Published in Canadian Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.6126

zbMATH Keywords

torusminorobstructionconnectivity 2

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Graph minors (05C83)

Abstract: The complete set of minimal obstructions for embedding graphs into the torus is still not determined. In this paper, we present all obstructions for the torus of connectivity 2. Furthermore, we describe the building blocks of obstructions of connectivity 2 for any orientable surface.

Recommendations

• A large set of torus obstructions and how they were discovered
• The obstructions for toroidal graphs with no \(K_{3,3}\)'s
• All minor-minimal apex obstructions with connectivity two
• Obstructions for simple embeddings
• On some minimal graphs of the torus

Cited in

(11)

• Excluded minors for the Klein bottle. I: Low connectivity case
• \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions
• Some excluded minors for the spindle surface
• Forbidden minors: finding the finite few
• Obstructions for two-vertex alternating embeddings of graphs in surfaces
• Minor obstructions for apex-pseudoforests
• On the connectivity of graphs embedded in surfaces. II
• Excluded minors for the Klein bottle. II: Cascades
• The obstructions for toroidal graphs with no \(K_{3,3}\)'s
• Sparse obstructions for minor-covering parameters
• A large set of torus obstructions and how they were discovered

This page was built for publication: Obstructions of connectivity two for embedding graphs into the torus

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