Strong Embeddings of 3-Connected Cubic Planar Graphs on Surfaces of non-negative Euler Characteristic
Discrete Mathematics & Theoretical Computer Science · 21.08.2026 · vol. 28:3 (Graph Theory)
DOI: 10.46298/dmtcs.16872 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, online erschienen am 21.08.2026. Verfasst von Meike Weiß und 1 weiteren Autor:innen.
Abstract (Originalsprache)
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.
Zitieren
APA
Weiß, M., & Niemeyer, A. C. (2026). Strong Embeddings of 3-Connected Cubic Planar Graphs on Surfaces of non-negative Euler Characteristic. Discrete Mathematics & Theoretical Computer Science, vol. 28:3(Graph Theory). https://doi.org/10.46298/dmtcs.16872
Vancouver
Weiß M, Niemeyer AC. Strong Embeddings of 3-Connected Cubic Planar Graphs on Surfaces of non-negative Euler Characteristic. Discrete Mathematics & Theoretical Computer Science. 2026;vol. 28:3(Graph Theory). doi:10.46298/dmtcs.16872
BibTeX
@article{Wei2026,
author = {Weiß, Meike and Niemeyer, Alice C.},
title = {Strong Embeddings of 3-Connected Cubic Planar Graphs on Surfaces of non-negative Euler Characteristic},
journal = {Discrete Mathematics & Theoretical Computer Science},
year = {2026},
volume = {vol. 28:3},
number = {Graph Theory},
doi = {10.46298/dmtcs.16872}
}
EUVIMED