pith. sign in

arxiv: 2407.17972 · v3 · pith:O7R7JZDVnew · submitted 2024-07-25 · 🧮 math.CO

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

Meike Wei{\ss} , Alice C. Niemeyer This is my paper

Pith reviewed 2026-05-25 08:32 UTC · model grok-4.3

classification 🧮 math.CO
keywords embeddingsstrongsurfacesconnectedembeddinggraphgraphsplanar
0
0 comments X

The pith

A complete characterization of strong embeddings on the projective plane, torus, and Klein bottle is given for 3-connected cubic planar graphs in terms of a distinguished subset of Enami's subgraphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Whitney showed that 3-connected planar graphs have a unique way to be drawn on a sphere without crossings. Enami later gave a condition for when such graphs can be embedded on other surfaces like the torus or projective plane: the dual graph must contain a certain subgraph. This work focuses on 'strong' embeddings, a stricter version relevant to the cycle double cover conjecture. It identifies exactly which of Enami's subgraphs allow strong embeddings on the projective plane, torus, and Klein bottle. As a result, the authors also give clear rules for when a graph cannot have such a strong embedding on these surfaces.

Core claim

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.

Load-bearing premise

The result assumes Enami's prior theorem that an embedding exists on these surfaces if and only if the dual contains a particular subgraph; the strong-embedding characterization is then obtained by restricting to a distinguished subset of those subgraphs.

Figures

Figures reproduced from arXiv: 2407.17972 by Alice C. Niemeyer, Meike Wei{\ss}.

Figure 1
Figure 1. Figure 1: The three graphs A3, A5 and A6 The correspondence between subgraphs of G∗ and re-embeddings of G is described more precisely in Remark 9. In Section 2 we first recall the definitions of combinatorial graph embeddings and then summarise the approach and results of [3]. The main result of this paper is proved in Section 3 after characterising when a re￾embedding is strong. Furthermore, in Section 4 we determ… view at source ↗
Figure 2
Figure 2. Figure 2: K4 embedded on the plane (a) and the projective plane (b) 2 Preliminaries In this section, we first consider graph embeddings and introduce a combinatorial way of describing them. Then we examine embeddings of 3-connected cubic planar graphs on surfaces with non-negative Euler char￾acteristic that are not homeomorphic to the sphere. We assume that all our graphs are undirected, connected, simple and finite… view at source ↗
Figure 3
Figure 3. Figure 3: Local change at vertex v with twisted edges coloured red To understand a graph embedding defined by an embedding scheme better, it is more intuitive to know the facial walks of the embedding. A well-known algorithm computes the facial walks of a given embedding by using the face traversal procedure described in Algorithm 1. The face traversal procedure takes as input an embedding scheme and computes one fa… view at source ↗
Figure 4
Figure 4. Figure 4: Planar embedding of K4 with twisted edge {1, 2} drawn in red 1. Start at vertex v = 1 with κ = 1 and edge f = {1, 2}. 2. Since λ(f) = −1, we set κ = −1. So the next edge we traverse is ρ −1 2 ({1, 2}) = {2, 4} = e, i.e. the anticlockwise successor of {1, 2} at 2. 3. λ(e) = 1, so κ is still −1. The next edge we traverse is ρ −1 4 ({2, 4}) = {1, 4} = e. 4. λ(e) = 1, so κ is still −1. The next edge we travers… view at source ↗
Figure 5
Figure 5. Figure 5: Segments of facial cycles (blue and orange) for [PITH_FULL_IMAGE:figures/full_fig_p006_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Re-embedding of K4 with the rotation system given by the planar embedding and all edges twisted (coloured in red) together with a facial cycle of the re-embedding coloured blue Each T defines an embedding of G, but we do not know yet on which surface this is an embedding. Enami characterises in [3] the sets T of twisted edges which yield embeddings on the projective plane, the torus and the Klein bottle. M… view at source ↗
Figure 7
Figure 7. Figure 7: The six graphs A1 to A6 With this characterisation, we obtain the following approach for computing all re-embeddings on surfaces with non-negative Euler characteristic for a given 3-connected cubic planar graph G. Algorithm 2: Re-embedding Algorithm Input: A 3-connected cubic graph G and a surface S on which we re-embed G Output: All re-embeddings of G on the given surface S 1. Compute the planar embedding… view at source ↗
Figure 8
Figure 8. Figure 8: b, has a subgraph isomorphic to K2,2, where the vertices of the partition sets of size two are not adjacent, and which are coloured red. The rotation system, defined by the drawing of G on the plane, together with the twisted edges, defined by K2,2, defines an embedding scheme called λ for G. By Theorem 10 λ defines a re-embedding of G on the torus. Since a torus is an orientable surface, there exists an e… view at source ↗
Figure 9
Figure 9. Figure 9: A face that has exactly two adjacent twisted edges [PITH_FULL_IMAGE:figures/full_fig_p009_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: A planar graph G (a) and its dual graph G∗ (b) with twisted edges coloured red and visited edges coloured teal Now, the goal is to employ the dual facial walks to characterise whether the re-embedding we consider is strong or not. Before we can get to that, we give a result on facial walks of G∗ that are not edge simple. We call a closed walk edge simple if all edges in this walk are distinct. Lemma 16. L… view at source ↗
Figure 11
Figure 11. Figure 11: K1,1,m We compute the facial walks of βT (HT ) with the face traversal procedure, starting at vertex x with the edge {x, y}. Then we obtain the facial walk (x, y, m, x, y, 1). This facial walk contains the edge {x, y} twice, so it is not a cycle and therefore βT (G) is not strong. Note that a closed cubic graph walk with distinct edges is a cycle. The following theorem leads to a criterion for deciding wh… view at source ↗
Figure 12
Figure 12. Figure 12: Embedding of HT in G∗ with twisted edges marked in red and visited edges marked in teal 3.1 Projective Plane In this section we consider strong re-embeddings of 3-connected cubic planar graphs on the projective plane, i.e. on a non-orientable surface of genus 1. Theorem 10 states that we need to find subgraphs of G∗ that are isomorphic to K2 or K4 for general re-embeddings of G on the projective plane. No… view at source ↗
Figure 13
Figure 13. Figure 13: Number of graphs in Gn for n ∈ {4, 6, 8, 10, 12, 14, 16, 18, 20} with strong re-embeddings on the projective plane Let G ∈ Gn. It is clear that each vertex of degree three in G∗ defines a subgraph of G∗ isomorphic to K4. Thus, all dual graphs of Gn that do not have a strong re-embedding on the projective plane have minimum degree at least four. The authors in [2] enumerate the number of plane triangulatio… view at source ↗
Figure 14
Figure 14. Figure 14: Planar embedding of K2,2,2 So twisted subgraphs which are isomorphic to K2,2,2 always lead to strong re-embeddings. For twisted subgraphs isomorphic to K2,2m we need to provide additional properties as shown in Lemma 24. Lemma 24. Let G be a 3-connected cubic planar graph and T ⊆ E(G) such that HT ∼= K2,m for m ≥ 2. The re-embedding βT (G) is strong if and only if the vertices of the partition sets of siz… view at source ↗
Figure 15
Figure 15. Figure 15: Planar embedding of HT ∪  {w1, w2} [PITH_FULL_IMAGE:figures/full_fig_p014_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Planar embedding of K2,m for m ≥ 2 14 [PITH_FULL_IMAGE:figures/full_fig_p014_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: In Figure 17a no vertex of B can be in ext(C˜) and in Figure 17b no vertex of B can be in int(C˜). w3 w1 w4 w2 . . . (a) w3 w1 w4 w2 . . . (b) [PITH_FULL_IMAGE:figures/full_fig_p015_17.png] view at source ↗
Figure 18
Figure 18. Figure 18: Number of graphs in Gn for n ∈ {4, 6, 8, 10, 12, 14, 16, 18, 20} with strong re-embeddings on the torus 3.3 Klein Bottle In this section we consider strong re-embeddings of 3-connected cubic planar graphs on the Klein bottle, i.e. on a non-orientable surface of genus 2. We have seen in the previous sections the adaptation of general re-embeddings on the projective plane and the torus to the case of strong… view at source ↗
Figure 19
Figure 19. Figure 19: Number of graphs in Gn for n ∈ {4, 6, 8, 10, 12, 14, 16, 18, 20} with strong re-embeddings on the Klein bottle 4 Existence of Strong Re-embeddings In [3], the author shows that there are for each 3-connected cubic planar graph re-embeddings on the projective plane, the torus and the Klein bottle. In the Figures 13, 18 and 19 we see that this is not true for strong re-embeddings. This can also be seen in t… view at source ↗
Figure 20
Figure 20. Figure 20: Graph G with two cycles of length 2n and G∗ ∼= K2,2n for n ≥ 1 5 Conclusion In this paper, we have identified existence conditions for strong graph embeddings of 3-connected cubic planar graphs on the projective plane, the torus and the Klein bottle. These results enable us to make statements about the existence or non-existence of embeddings of a given 3-connected cubic planar graph on one of these three… view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript extends Enami's theorem on embeddings of 3-connected cubic planar graphs on the projective plane, torus, and Klein bottle (which exist iff the dual contains a particular subgraph) by characterizing strong embeddings via a distinguished subset of those subgraphs. It derives explicit criteria for when a graph does not admit a strong embedding on these surfaces, motivated by connections to the cycle double cover conjecture and triangulated surfaces.

Significance. If the characterization is correct, the work strengthens the structural theory of embeddings on surfaces of non-negative Euler characteristic and supplies concrete tools for identifying non-embeddable cases, with direct relevance to algorithmic computation of cycle double covers. The explicit non-existence criteria constitute a clear applied contribution.

minor comments (2)
  1. [Introduction] The definition of 'strong embedding' (and the precise distinction of the 'distinguished subset') should be stated explicitly in the introduction or §2 rather than deferred entirely to Enami's prior work, to make the manuscript self-contained for readers.
  2. [Abstract] The abstract refers to 'Enami's subgraphs' without a forward reference to the section where the distinguished subset is defined; adding such a pointer would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, assessment of significance, and recommendation of minor revision. The report lists no specific major comments.

Circularity Check

0 steps flagged

No significant circularity; characterization builds on external Enami theorem

full rationale

The paper derives its central characterization of strong embeddings by restricting Enami's subgraphs (from an external prior theorem on embedding existence) to a distinguished subset. No equations, fitted parameters, or self-definitional reductions appear. The result does not reduce to any self-citation chain or ansatz smuggled from the authors' prior work; Enami is cited as an independent source. The derivation chain is therefore self-contained against external benchmarks and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper is a pure combinatorial characterization that rests on standard graph-theoretic background and one cited existence theorem.

axioms (2)
  • standard math Standard definitions and properties of 3-connected cubic planar graphs, their duals, and embeddings on surfaces of non-negative Euler characteristic
    Invoked throughout as the ambient setting for the characterization.
  • domain assumption Enami's theorem that an embedding exists iff the dual contains a particular subgraph
    The strong-embedding result is obtained by selecting a subset of those subgraphs; the paper therefore inherits this existence criterion.

pith-pipeline@v0.9.0 · 5688 in / 1306 out tokens · 29225 ms · 2026-05-25T08:32:14.323736+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    J. D. Beule, J. Jonuˇ sas, J. D. Mitchell, M. Torpey, M. Tsalakou, and W. A. Wilson. Digraphs - GAP package, version 1.6.3, Sep 2023

    work page 2023

  2. [2]

    M. B. Dillencourt. Polyhedra of small order and their Hamiltonian properties. J. Combin. Theory Ser. B, 66(1):87–122, 1996

    work page 1996

  3. [3]

    K. Enami. Embeddings of 3-connected 3-regular planar graphs on surfaces of non-negative Euler char- acteristic. Discrete Math. Theor. Comput. Sci. , 21(4):Paper No. 11, 19, 2019

    work page 2019

  4. [4]

    GAP – Groups, Algorithms, and Programming, Version 4.12.2 , 2022

    The GAP Group. GAP – Groups, Algorithms, and Programming, Version 4.12.2 , 2022

    work page 2022

  5. [5]

    J. L. Gross and T. W. Tucker. Topological graph theory. Wiley-Interscience Series in Discrete Mathe- matics and Optimization. John Wiley & Sons Inc., New York, 1987

    work page 1987

  6. [6]

    F. Jaeger. A survey of the cycle double cover conjecture. In Cycles in graphs (Burnaby, B.C., 1982) , volume 115 of North-Holland Math. Stud. , pages 1–12. North-Holland, Amsterdam, 1985

    work page 1982

  7. [7]

    Kitakubo and S

    S. Kitakubo and S. Negami. Re-embedding structures of 5-connected projective-planar graphs. Discrete Mathematics, 244:211–221, 02 2002

    work page 2002

  8. [8]

    J. R. Kline. What is the jordan curve theorem? The American Mathematical Monthly , 49(5):281–286, 1942

    work page 1942

  9. [9]

    B. Mohar. Strong embeddings of minimum genus. Discrete Math., 310(20):2595–2599, 2010

    work page 2010

  10. [10]

    Mohar and N

    B. Mohar and N. Robertson. Planar graphs on nonplanar surfaces. J. Combin. Theory Ser. B , 68(1):87– 111, 1996

    work page 1996

  11. [11]

    Mohar, N

    B. Mohar, N. Robertson, and R. P. Vitray. Planar graphs on the projective plane. Discrete Math. , 149(1-3):141–157, 1996

    work page 1996

  12. [12]

    Mohar and C

    B. Mohar and C. Thomassen. Graphs on Surfaces. Johns Hopkins University Press, 2001

    work page 2001

  13. [13]

    S. Negami. Uniqueness and faithfulness of embedding of toroidal graphs. Discrete Math., 44(2):161–180, 1983

    work page 1983

  14. [14]

    R. B. Richter, P. D. Seymour, and J. ˇSir´ aˇ n. Circular embeddings of planar graphs in nonspherical surfaces. Discrete Math., 126(1-3):273–280, 1994

    work page 1994

  15. [15]

    Y. Suzuki. Re-embedding structures of 4-connected projective-planar graphs. J. Graph Theory , 68(3):213–228, 2011

    work page 2011

  16. [16]

    Thomassen

    C. Thomassen. The graph genus problem is NP-complete. J. Algorithms, 10(4):568–576, 1989

    work page 1989

  17. [17]

    Thomassen

    C. Thomassen. Embeddings of graphs with no short noncontractible cycles. J. Combin. Theory Ser. B , 48(2):155–177, 1990

    work page 1990

  18. [18]

    Thomassen

    C. Thomassen. The genus problem for cubic graphs. J. Combin. Theory Ser. B , 69(1):52–58, 1997

    work page 1997

  19. [19]

    M. Weiß. https://github.com/MeikeWeiss/SimplicialEmbeddings

    work page

  20. [20]

    H. Whitney. 2-Isomorphic Graphs. Amer. J. Math. , 55(1-4):245–254, 1933. 19

    work page 1933