Weiß and Niemeyer (2024, published 2026) completed the structural theory of strong embeddings of 3-connected cubic planar graphs on the three non-spherical surfaces of non-negative Euler characteristic — the projective plane, the torus, and the Klein bottle — by proving a one-to-one correspondence between inequivalent strong embeddings and distinguished subgraphs of the planar dual graph. The open problem is to extend this characterization to surfaces of negative Euler characteristic: for each orientable surface of genus g≥2g \geq 2 and each non-orientable surface of crosscap number k≥3k \geq 3, describe the inequivalent strong embeddings of a 3-connected cubic planar graph on that surface through an explicit correspondence with subgraphs of the dual, together with exact existence criteria and the structural basis for enumerating such embeddings. Recent work resolves adjacent questions — aggregate orientable existence via Apollonian duals, and a classification of all 2-cell embeddings of orientable genus 2 for cyclically 5-edge-connected graphs — but no per-surface characterization of strong embeddings on any surface of negative Euler characteristic is known.

Background

A 2-cell (cellular) embedding of a graph GG in a closed surface SS is a drawing in which edges intersect only at shared endpoints and every face is homeomorphic to an open disk; the boundary of a face is read off as a facial walk. Combinatorially, an embedding is encoded by an embedding scheme: a rotation system, that is, a cyclic ordering of the incident edges at each vertex, together with a signature marking certain edges as twisted (an edge across which the two local sides of the surface are interchanged); a scheme realizes an embedding on a non-orientable surface precisely when some cycle contains an odd number of twisted edges, and two embedding schemes are equivalent if one is obtained from the other by a sequence of local changes, that is, reversing the rotation at a vertex while flipping the signatures of the edges incident with it, which corresponds to equivalence of embeddings under homeomorphisms of the ambient surface. A strong embedding, also called a circular or closed 2-cell embedding, is a 2-cell embedding in which every facial walk is a single cycle, i.e. no face boundary revisits a vertex. Orientable surfaces are classified by their genus gg (number of handles) and non-orientable surfaces by their crosscap number kk; the Euler characteristic is 2−2g2 - 2g in the orientable case and 2−k2 - k in the non-orientable case, so the surfaces of negative Euler characteristic are exactly the orientable surfaces of genus g≥2g \geq 2 and the non-orientable surfaces of crosscap number k≥3k \geq 3. Strong embeddings matter for two reasons. First, the face boundaries of a strong embedding form a circuit double cover — a collection of cycles of GG covering every edge exactly twice — so strong embeddings are a route to the circuit double cover (CDC) conjecture of Jaeger, which asserts that every bridgeless graph admits such a cover; the orientable version asks for a strong embedding of every 2-connected graph on some orientable surface. Second, in the theory of simplicial surfaces (combinatorial incidence structures of triangulated surfaces), the face graph — the graph formed by the edges and vertices of the triangulation — is always cubic, and computing all simplicial surfaces with a given face graph GG is equivalent to computing all strong embeddings of GG; this equivalence drives a computational program built on the GAP computer algebra system and its SimplicialSurfaces package.

By Whitney's uniqueness theorem, a 3-connected planar graph has a unique embedding on the sphere, hence a unique planar dual G∗G^{*}. Enami (2019) studied embeddings (not necessarily strong) of 3-connected cubic planar graphs on the three non-spherical surfaces of non-negative Euler characteristic and characterized them through subgraphs of G∗G^{*}: for instance, the embeddings on the torus correspond to subgraphs of G∗G^{*} isomorphic to K2,2,2K_{2,2,2}, K2,2mK_{2,2m}, or K1,1,2m−1K_{1,1,2m-1} (complete multipartite graphs, with m≥1m \geq 1). Weiß and Niemeyer refined this to strong embeddings: their Theorem 1 gives a one-to-one correspondence between inequivalent strong embeddings of a 3-connected cubic planar graph GG and subgraphs of G∗G^{*} isomorphic to K4K_{4} (projective plane); to K2,2,2K_{2,2,2} or K2,2mK_{2,2m} with m≥1m \geq 1, where for K2,2mK_{2,2m} the two vertices of the size-2 partition class are non-adjacent in G∗G^{*} (torus); and to one of three small explicit graphs A3,A5,A6A_{3}, A_{5}, A_{6} or to K2,2m−1K_{2,2m-1} with m≥2m \geq 2, again with the non-adjacency condition (Klein bottle). This yields exact existence and non-existence criteria, an implementation for computing such embeddings in GAP, and the conclusion that some graphs have exponentially many strong embeddings on the torus and the Klein bottle.

The surrounding theory shows the higher-genus regime is genuinely different. Richter, Seymour, and Širáň (1994) proved that every 3-connected planar graph admits a strong embedding on some non-spherical surface, while Mohar (2010) constructed cubic graphs that admit strong embeddings only on surfaces whose genus grows proportionally to their number of vertices, refuting a folklore conjecture of Tutte; so no bounded family of surfaces suffices for cubic graphs in general. The extension to higher genus also has to contend with the theory of planar graphs on nonplanar surfaces developed by Mohar and Robertson and by Mohar, Robertson, and Vitray, on which Enami's proof rests. Two 2025–2026 developments delimit what is already known. Weiß, Akpanya, and Niemeyer (2025) showed that the isomorphism classes of strong embeddings on the three small surfaces correspond to orbits of Aut(G∗)\mathrm{Aut}(G^{*}) on the distinguished dual subgraphs, computed a database of all such classes for graphs with up to 22 vertices, proved that every cyclically 4-edge-connected cubic planar graph (a graph in which no edge cut of size less than 4 separates two cycles) has a strong embedding on some orientable surface of positive genus, and characterized the obstruction: a 3-connected cubic planar graph has no strong embedding on any orientable surface of positive genus if and only if it is an Apollonian dual, i.e. the dual of an Apollonian network (a planar triangulation generated by repeatedly inserting a new vertex into a triangular face). A companion paper (2026) extends this unique-cover characterization to all 3-connected planar graphs. Separately, Carr and Mohar (2026) introduced the unstable dual of a 2-cell embedding of a cubic graph — the subgraph of the dual recording where the embedding deviates from the planar one — and used it to characterize all 2-cell embeddings of orientable genus 2 of cyclically 5-edge-connected cubic planar graphs; they explicitly leave genus k≥3k \geq 3 (and genus 2 for graphs that are not cyclically 5-edge-connected) as open questions, observing that the candidate subgraph families already proliferate at genus 3. None of this work isolates the strong embeddings on any fixed surface of negative Euler characteristic, and the non-orientable side (crosscap number at least 3) is untouched.

Problem Statement

For a 3-connected cubic planar graph GG with (by Whitney's uniqueness theorem, well-defined) planar dual G∗G^{*}, and for each compact surface SS of negative Euler characteristic — each orientable surface of genus g≥2g \geq 2 and each non-orientable surface of crosscap number k≥3k \geq 3 — characterize the inequivalent strong embeddings of GG on SS. The characterization is demanded for the entire family of such surfaces, not merely for the smallest instances. The required form of the characterization, generalizing Theorem 1 of Weiß and Niemeyer for the projective plane, torus, and Klein bottle, is an explicit one-to-one correspondence between the inequivalent strong embeddings of GG on SS and distinguished subgraphs of G∗G^{*} (specified families of subgraph types with side conditions, such as non-adjacency requirements in G∗G^{*}), where two embeddings count as equivalent when their embedding schemes differ only by local changes, equivalently when a homeomorphism of the ambient surface carries one onto the other. This characterization must also determine two consequences: (a) an exact existence criterion determining precisely which 3-connected cubic planar graphs admit a strong embedding on SS; and (b) the structural foundation it provides for enumerating and counting strong embeddings (or their isomorphism classes, two strong embeddings being isomorphic when their corresponding sets of facial cycles lie in the same orbit under Aut(G)\mathrm{Aut}(G)) on SS, in the spirit of the GAP-based computations already carried out for the three surfaces of non-negative Euler characteristic. The first open instances — the smallest cases of this general problem, and the natural starting points for resolving it — are the orientable surface of genus 2 and the non-orientable surface of crosscap number 3; for orientable genus 2, any answer must be consistent with (and is constrained, but not determined, by) the Carr–Mohar classification of all 2-cell embeddings of cyclically 5-edge-connected cubic planar graphs.

References

  1. Meike Weiß and Alice C. Niemeyer, Strong Embeddings of 3-Connected Cubic Planar Graphs on Surfaces of non-negative Euler Characteristic, Discrete Mathematics & Theoretical Computer Science 28(3) (2026), published version DOI 10.46298/dmtcs.16872, preprint arXiv:2407.17972, https://arxiv.org/abs/2407.17972
  2. Kengo Enami, Embeddings of 3-connected 3-regular planar graphs on surfaces of non-negative Euler characteristic, Discrete Mathematics & Theoretical Computer Science 21(4), Paper No. 14 (2019), DOI 10.23638/dmtcs-21-4-14, preprint arXiv:1806.11333, https://doi.org/10.23638/dmtcs-21-4-14
  3. Meike Weiß, Reymond Akpanya, and Alice C. Niemeyer, On 3-Connected Cubic Planar Graphs and their Strong Embeddings on Orientable Surfaces, arXiv:2509.14964 (2025), https://arxiv.org/abs/2509.14964
  4. Meike Weiß, Reymond Akpanya, and Alice C. Niemeyer, On 3-Connected Planar Graphs with Unique Orientable Circuit Double Covers, arXiv:2601.10171 (2026), https://arxiv.org/abs/2601.10171
  5. MacKenzie Carr and Bojan Mohar, 2-cell embeddings of cubic graphs I. The unstable dual, arXiv:2606.06768 (2026), https://arxiv.org/abs/2606.06768
  6. R. B. Richter, P. D. Seymour, and J. Širáň, Circular embeddings of planar graphs in nonspherical surfaces, Discrete Mathematics 126(1-3) (1994), 273-280, DOI 10.1016/0012-365X(94)90271-2, https://doi.org/10.1016/0012-365X(94)90271-2
  7. Bojan Mohar, Strong embeddings of minimum genus, Discrete Mathematics 310(20) (2010), 2595-2599, DOI 10.1016/j.disc.2010.03.019 (preprint arXiv:0908.1933), https://arxiv.org/abs/0908.1933
  8. Bojan Mohar and Neil Robertson, Planar graphs on nonplanar surfaces, Journal of Combinatorial Theory, Series B 68(1) (1996), 87-111, DOI 10.1006/jctb.1996.0058, https://doi.org/10.1006/jctb.1996.0058
  9. Bojan Mohar, Neil Robertson, and Richard P. Vitray, Planar graphs on the projective plane, Discrete Mathematics 149(1-3) (1996), 141-157, DOI 10.1016/0012-365X(94)00349-N, https://doi.org/10.1016/0012-365X(94)00349-N
  10. F. Jaeger, A survey of the cycle double cover conjecture, in Cycles in graphs (Burnaby, B.C., 1982), North-Holland Mathematics Studies 115, North-Holland, Amsterdam (1985), 1-12, DOI 10.1016/S0304-0208(08)72993-1, https://doi.org/10.1016/S0304-0208(08)72993-1
  11. Hassler Whitney, 2-Isomorphic Graphs, American Journal of Mathematics 55(1-4) (1933), 245-254, DOI 10.2307/2371127, https://doi.org/10.2307/2371127
  12. Babak Ghanbari and Robert Šámal, Facial diagrams and cycle double cover, arXiv:2605.01410 (2026), https://arxiv.org/abs/2605.01410