Obstructions of connectivity two for embedding graphs into the torus

DOI10.4153/CJM-2014-025-XzbMATH Open1303.05040arXiv1207.6126OpenAlexW2963327335MaRDI QIDQ2933708FDOQ2933708

Authors: Bojan Mohar, Petr Škoda 

Publication date: 5 December 2014

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

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.

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

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

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)

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
• Excluded minors for the Klein bottle. II: Cascades
• On the connectivity of graphs embedded in surfaces. II
• 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)