Strong embeddings of minimum genus

DOI10.1016/J.DISC.2010.03.019zbMATH Open1221.05090arXiv0908.1933OpenAlexW2117152550MaRDI QIDQ709302FDOQ709302

Authors: Bojan Mohar 

Publication date: 18 October 2010

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: A "folklore conjecture, probably due to Tutte" (as described in [P.D. Seymour, Sums of circuits, Graph theory and related topics (Proc. Conf., Univ. Waterloo, 1977), pp. 341-355, Academic Press, 1979]) asserts that every bridgeless cubic graph can be embedded on a surface of its own genus in such a way that the face boundaries are cycles of the graph. In this paper we consider closed 2-cell embeddings of graphs and show that certain (cubic) graphs (of any fixed genus) have closed 2-cell embedding only in surfaces whose genus is very large (proportional to the order of these graphs), thus providing plethora of strong counterexamples to the above conjecture. The main result yielding such counterexamples may be of independent interest.

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

Recommendations

• On minimum-genus embeddings
• A note on strong embeddings of maximal planar graphs on non-orientable surfaces
• Maximum genus of strong embeddings
• Strong embeddings of planar graphs on higher surfaces
• Densely embedded graphs

zbMATH Keywords

cubic graphgenuscycle double coverface widthstrong embeddingcircular embedding

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)

Cites Work

• Graphs on surfaces
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reducible configurations for the cycle double cover conjecture
• Crossing number and weighted crossing number of near-planar graphs
• Combinatorial Local Planarity and the Width of Graph Embeddings
• Circular embedding of planar graphs in nonspherical surfaces
• Closed 2-cell embeddings of 5-crosscap embeddable graphs
• The closed 2-cell embeddings of 2-connected doubly toroidal graphs
• On minimum-genus embeddings
• Orientable embeddings and orientable cycle double covers of projective-planar graphs
• Crossing and Weighted Crossing Number of Near-Planar Graphs

Cited In (9)

• Maximum genus of strong embeddings
• Uniform strong 2-cell embeddings of bridgeless graphs
• Strong embedding of HP-graphs on surface with higher genus
• Constructing all minimum genus embeddings of
• Nonorientable strong maximum genus of maximal outplanar graph
• Densely embedded graphs
• Closed 2-cell embeddings of graphs with no \(V_8\)-minors
• Title not available (Why is that?)
• Circuit Double Covers of Graphs

This page was built for publication: Strong embeddings of minimum genus

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