Strong embeddings of minimum genus

DOI10.1016/J.DISC.2010.03.019MaRDI QIDQ709302zbMATH OpenOpenAlexFDO

Authors Bojan Mohar

Publication date 18 October 2010

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

Cited in

(11)

• Maximum genus of strong embeddings
• Circuit double covers of graphs
• Strong embeddings and 2-isomorphism
• 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₈-minors
• scientific article; zbMATH DE number 1006489 (Why is no real title available?)
• On the genera of polyhedral embeddings of cubic graph

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)