Abstract:Whitney proved that 3-connected planar graphs admit a unique embedding on the sphere. In contrast, Enami investigated embeddings of 3-connected cubic planar graphs on non-spherical surfaces with non-negative Euler characteristic. He established that such an embedding exists if and only if the dual graph contains a particular subgraph. Here, strong embeddings are investigated motivated by the cycle double cover conjecture and the relation to triangulated surfaces. We provide a complete characterization of strong embeddings on the projective plane, the torus, and the Klein bottle in terms of a distinguished subset of Enami's subgraphs. This characterization not only deepens the structural understanding of graph embeddings on non-spherical surfaces, but also establishes a robust foundation for computing cycle double covers. As a direct consequence, we derive explicit criteria that determine when a graph does not admit a strong embedding on these surfaces-offering new tools for both theoretical analysis and algorithmic applications.
| Subjects: | Combinatorics (math.CO) |
| Cite as: | arXiv:2407.17972 [math.CO] |
| (or arXiv:2407.17972v3 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2407.17972 arXiv-issued DOI via DataCite |
From: Meike Weiß [view email]
[v1]
Thu, 25 Jul 2024 12:07:28 UTC (152 KB)
[v2]
Wed, 5 Nov 2025 13:43:07 UTC (151 KB)
[v3]
Fri, 22 May 2026 08:17:55 UTC (155 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。