EUVIMEDEUVIMED entdecken
Crossref

Strong Embeddings of 3-Connected Cubic Planar Graphs on Surfaces of non-negative Euler Characteristic

Meike Weiß, Alice C. Niemeyer

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →